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 (node 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 2h+1–1. Since, there are h levels we need to add all nodes a teach level. [20+21+22+···+2h =2h+1–1].
- The number of nodes n in a complete binary tree is between 2h (minimum) and 2h+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).
