# Tree Data Structure

**What is Tree ? Terminologies and Explanation**

A *tree *is a data structure similar to a linked list but instead of each node pointing simply to the next node in a linear fashion, each node points to a number of nodes. Tree is an example of a non- linear data structure. A *tree *structure is a way of representing the hierarchical nature of a structure in a graphical form.

- The
*root*of a tree is the node with no parents. There can be at most one root node in a tree (*n*ode*A*in the above example). - An
*edge*refers to the link from parent to child (all links in the figure). - A node with no children is called
*leaf*node (*E,J,K,H*and*I*). - Children of same parent are called
*siblings*(*B,C,D*are siblings of*A*, and*E,F*are the siblings of*B*). - A node p is an
*ancestor*of node*q*if there exists a path from*root*to*q*and p appears - on the path. The node
*q*is called a*descendant*of p. For example,*A,C*and*G*are the ancestors of if. - The set of all nodes at a given depth is called the
*level*of the tree (*B, C*and*D*are the same level). The root node is at level zero.

- The
*depth*of a node is the length of the path from the root to the node (depth of*G*is 2,*A*—*C*—*G*). - The
*height*of a node is the length of the path from that node to the deepest node. The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero. In the previous example, the height of*B*is 2 (*B*—*F*—*J*). *Height of the tree*is the maximum height among all the nodes in the tree and*depth of the tree*is the maximum depth among all the nodes in the tree. For a given tree, depth and height returns the same value. But for individual nodes we may get different results.- The size of a node is the number of descendants it has including itself (the size of the subtree
*C*is 3). - If every node in a tree has only one child (except leaf nodes) then we call such trees
*skew trees*. If every node has only left child then we call them*left skew trees*. Similarly, if every node has only right child then we call them*right skew trees.*

**Binary Trees**

A tree is called *binary tree *if each node has zero child, one child or two children. Empty tree is also a valid binary tree. We can visualize a binary tree as consisting of a root and two disjoint binary trees, called the left and right subtrees of the root.

**Types of Binary Trees**

**Strict Binary Tree: **A binary tree is called *strict binary tree *if each node has exactly two children or no children.

**Full Binary Tree: **A binary tree is called *full binary tree *if each node has exactly two children and all leaf nodes are at the same level.

**Complete Binary Tree: **Before defining the *complete binary tree*, let us assume that the height of the binary tree is *h*. In complete binary trees, if we give numbering for the nodes by starting at the root (let us say the root node has 1) then we get a complete sequence from 1 to the number of nodes in the tree. While traversing we should give numbering for NULL pointers also. A binary tree is called *complete binary tree *if all leaf nodes are at height *h *or *h *— 1 and also without any missing number in the sequence.

**Properties of Binary Trees**

For the following properties, let us assume that the height of the tree is *h*. Also, assume that root node is at height zero.

From the diagram we can infer the following properties:

- The number of nodes n in a full binary tree is 2
*h+*1–1. Since, there are*h*levels we need to add all nodes a teach level. [20+21*+*22+···+2*h*=2*h+*1*–*1]. - The number of nodes
*n*in a complete binary tree is between 2*h*(minimum) and 2*h+*1–1 (maximum). For more information on this, refer to*Priority Queues*chapter. - The number of leaf nodes in a full binary tree is 2 .
- The number of NULL links (wasted pointers) in a complete binary tree of n nodes is
*n*+ 1.

**Structure of Binary Trees**

**Basic Operations**

- Inserting an element into a tree
- Deleting an element from a tree
- Searching for an element
- Traversing the tree

**Auxiliary Operations**

- Finding the size of the tree
- Finding the height of the tree
- Finding the level which has maximum sum
- Finding the least common ancestor (LCA) for a given pair of nodes, and many more.

**Applications of Binary Trees**

Following are the some of the applications where *binary trees *play an important role:

- Expression trees are used in compilers.
- Huffman coding trees that are used in data compression algorithms.
- Binary Search Tree (BST), which supports search, insertion and deletion on a collection of items in O(
*logn*) (average). - Priority Queue (PQ), which supports search and deletion of minimum (or maximum) on a collection of items in logarithmic time (in worst case).