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.

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

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

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

PREORDER-TREE-WALK (x):

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

## Discussion (0)