Binary Search Trees

A binary search tree (BST), a special form of a binary tree, satisfies the binary search property:

  1. The value in each node must be greater than (or equal to) any values stored in its left subtree.

  2. The value in each node must be less than (or equal to) any values stored in its right subtree.

Important Properties of BST

  1. InOrder traversal is not an unique identifier for BST

  2. PreOrder and PostOrder are unique identifiers of BST

  3. inOrder = sorted(preOrder) + sorted(postOrder)

  4. InOrder + PreOrder and InOrder + PostOrder are unique identifiers of BST and be used to reconstruct the BST

PreviousConstruct Binary Tree based on inorder and postorderNextValidating BST

Last updated

Was this helpful?