DEV Community


Posted on

Binary Search Trees

A Binary Search tree is organized in a Binary Tree. Such a tree can be defined by a linked data structure in which a particular node is an object. In addition to a key field, each node contains field left, right, and p that point to the nodes corresponding to its left child, its right child, and its parent, respectively. If a child or parent is missing, the appropriate field contains the value NIL. The root node is the only node in the tree whose parent field is Nil.

  1. In-Order-Tree-Walk (x): Always prints keys in binary search tree in sorted order.

INORDER-TREE-WALK (x) - Running time is θ(n)

  1. If x ≠ NIL.
  2. then INORDER-TREE-WALK (left [x])
  3. print key [x]
  4. INORDER-TREE-WALK (right [x])
    1. PREORDER-TREE-WALK (x): In which we visit the root node before the nodes in either subtree.


  1. If x ≠ NIL.
  2. then print key [x]
  3. PREORDER-TREE-WALK (left [x]).
  4. PREORDER-TREE-WALK (right [x]).

Top comments (0)