# Introduction to trees and its terminologies

Learn: In this article we are going to study about **introduction of trees**. What is **generalized tree**? What are **different terminologies of tree**? Why we use trees? What are **benefits of use of trees**?

Submitted by Amit Shukla, on October 04, 2017

## Tree

**A tree is a collection of elements called nodes. Each node contains some value or element**. We will use the term node, rather than vertex with binary tree. Node is the main component of any tree structure. It stores the actual data along with links to other nodes.

### Key properties of Tree

**A tree T is represented by nodes and edges, which includes:**

**T**is empty (called null or empty tree).**T**has a left subtree and right subtree.

**Example**

### Tree Terminologies

**Consider the following tree**

**1. Root**

This is the unique node in the tree in which further subtrees were attached. **A** root node of a tree has its child. Left child and right child are the two childes a root node can have in a tree. In the given figure **A** is the root node.

**2. Degree of Node**

The total number of subtree attached to that node is called the degree of the node. **For node A the degree is 3**, **for node E the degree is 0**.

**3. Leaf Nodes**

These are the terminals nodes of the tree. The nodes which have degree 0 are called as leaf nodes of the tree. These nodes are always present at the end of the tree. Here in our example **E**, **F**, **C**, **G**, **H** are the leaf nodes of the tree.

**4. Internal Nodes**

The nodes in the tree which are other than leaf nodes and the root node are called as internal nodes. These nodes are present in between root node and leaf nodes in the tree that’s why these nodes are called as internal node. Here, **B and D are internal nodes**.

**5. Parent Node**

The node which is having further sub branches is called the parent node of those sub branches. In the above figure node **B** is the parent node of **E**, **F**, and **G** node and **E**, **F**, and **G** are called children of **B**.

**6. Predecessor**

While displaying the tree, if some particular nodes previous to some other nodes than that node is called the predecessor of the other node. In our example, **the node E is predecessor of node B**.

**7. Successor**

The node which occurs next to some other node is called successor of that node. In our example, **B is successor of F and G**.

**8. Level of tree**

The root node is always considering at level zero, and then its adjacent children are supposed to be at level 1 and so on. To understand the concept of level, see the above figure, the **node A** is at level 0, the **node B**, **C**, **D** are at level 1, the **nodes E**, **F**, **G**, **H** are at level 2.

**9. Height of the tree**

The maximum level is the height of the tree. Here **the height of the tree is 3**. The other terminology used for the height of the tree is depth of the tree.

**10. Forest**

A tree may be defined as a forest in which only a single node (root) has no predecessor Any forest is consist of collection of trees.

**11. Degree of tree**

The maximum degree of the node in the tree is called the degree of the tree. Here, the **degree of tree is 3**.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions