What is binary tree? Discuss the array representation of binary tree.

Answer: – A binary search tree is a binary tree that is either empty or in which each node passes a Key that satisfied the fallowing condition.

  1. All Keys in the left sub tree of the root precede the key in the root.
  2. The key in the root precedes all keys in its right sub tree.
  3. The left and right sub trees of the root are again search trees.

To search for the target, we first compare it with the key at the root of the tree. If it not same, we go to either left sub tree or right sub tree as appropriate and repeat the search in that sub tree. If we find the key, the function succeeds. If not, then we continued searching until we find and empty sub tree. If no element searched at the end means searching in finished and no element is found.

Arrays can be used to represent complete binary trees. Remember that in a complete binary tree, all of the depths are full, except perhaps for the deepest. At the deepest depth, the nodes are as far left as possible. For example, below is a complete binary tree with 9 nodes; each node contains a character. In this example, the first 7 nodes completely fill the levels at depth 0 (the root), depth 1 (the root’s children), and depth 2. There are 2 nodes at depth 3, and these are as far left as possible.

The 9 characters that the tree contains can be stored in an array of characters, starting with the root’s character in the [0] location, the 2 nodes with depth 1 are placed after the root, and so on. The entire representation of the tree by an array is shown in the figure below.

Binary Tree.png

Advertisements