Binary Tree Data Structure

Properties of binary tree

Types of Binary Tree

Binary Search Tree

Binary Search Tree

  1. The search binary tree data structure supports many dynamic-set operations, including SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT,and DELETE. Thus, we can use a search tree both as a dictionary and as a priority queue.

  2. Basic operations on a binary search tree take time proportional to the height of the tree. For a complete binary tree with n nodes, such operations run in Θ(lg n). If the tree is a linear chain of n nodes, however, the same operations take Θ(n) worst-case time.

  3. A tree by a linked data structure in which each node is an object. In addition to a key and satellite data, each node contains attributes left, right,and p that point to the nodes corresponding to its left child, right child and parent node respectively.

  4. If a child or the parent is missing, the appropriate attribute contains the value NIL. The root node is the only node in the tree whose parent is NIL.

  5. Binary search Tree property states that: Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y.key ≤ x.key. If y is a node in the right subtree of x,then y.key ≥ x.key.

  6. binary search tree
  7. The binary-search-tree property allows us to print out all the keys in a binary search tree in sorted order by a simple recursive algorithm, called an inorder tree walk. This algorithm is so named because it prints the key of the root of a subtree between printing the values in its left subtree and printing those in its right subtree. (Similarly, a preorder tree walk prints the root before the values in either subtree, and a postorder tree walk prints the root after the values in its subtrees.)

Binary Search Tree - Operations

  2. if x ≠ NIL
  3.     INORDER-TREE-WALK(x.left)
  4.     print(x.key)
  5.     INORDER-TREE-WALK(x.right)

If x is the root of an n-node subtree, then the call INORDER-TREE-WALK(x) takes Θ(n) time.

  1. TREE-SEARCH(x,k)
  2. if x ==NIL OR k == x.key
  3.     return x
  4. if k < x.key
  5.    return TREE-SEARCH(x.left,k)
  6. else return TREE-SEARCH(x.right,k)

Running time of TREE-SEARCH is O(h), where h is the height of the tree.

  1. TREE-Minimum(x)
  2. while x.left ≠ NIL
  3.     x = x.left
  4. return x

  1. TREE-Maximum(x)
  2. while x.right ≠ NIL
  3.     x = x.right
  4. return x

Running time of TREE-Minimum(x) and TREE-Minimum(x) is O(h), where h is the height of the tree.

  1. TREE-Successor(x)
  2. if x.right ≠ NIL
  3.     return TREE-Minimum(x.right)
  4. y = x.p
  5. while y ≠ NIL and x == y.right
  6.     x = y
  7.     y = y.p
  8. return y

Running time of TREE-Successor(x) and TREE-Predecessor(x) is O(h), where h is the height of the tree.

  2. y = NIL
  3. x = T.root
  4. while x ≠ NIL
  5.    y = x
  6.    if z.key < x.key
  7.       x = x.left
  8.    else x = x.right
  9. z.p = y 
  10. if y == NIL 
  11.    T.root = z
  12. else if z.key < y.key 
  13.    y.left = z
  14. else y.right = z 

Like the other primitive operations on search trees, the procedure T REE-INSERT runs in O(h) time on a tree of height h.

Binary Search Tree - Deletion Operation

  1. If z (node to be deleted) has no children, then we simply remove it by modifying its parent to replace z with NIL as its child.

  2. If z has just one child, then we elevate that child to take z’s position in the tree by modifying z’s parent to replace z by z’s child.

  3. If z has two children, then we find z’s successor y — which must be in z’s right subtree - and have y take z’s position in the tree. The rest of z’s original right subtree becomes y’s new right subtree, and z’s left subtree becomes y’s new left subtree.

  4. binary search tree - deletion

  2. if z.LEFT == NIL
  3.    TRANSPLANT(T,z,z.right)
  4. elseif z.RIGHT == NIL
  5.    TRANSPLANT(T,z,z.left)
  6. else y = TREE-MINIMUM.(z.right)
  7.    if y.p ≠ z
  8.       TRANSPLANT(T,y,y.right)
  9.       y.right = z.right
  10.       y.right.p = y
  11.    TRANSPLANT(T,z,y)
  12.    y.left = z.left
  13.    y.left.p = y

  1. TRANSPLANT(T,u,v)
  2. if u.p == NIL
  3.    T.root = v
  4. elseif u == u.p.left
  5.    u.p.left = v
  6. else u.p.right = v
  7. if v ≠ NIL
  8.    v.p = u.p

TREE-DELETE runs in O(h) time on a tree of height h.

Binary Tree Traversals - Inorder, Preorder, Postorder

Q. Perform Inorder, Preorder and Postorder traversal of a binary search tree

Previous Next