Skip to content
This repository has been archived by the owner on Jan 21, 2019. It is now read-only.

Latest commit

 

History

History
17 lines (11 loc) · 817 Bytes

Readme.md

File metadata and controls

17 lines (11 loc) · 817 Bytes

Binary Search Tree

It is an ordered tree data structure with two leaves per node. The ideal data structure to represent sorted data. In binary search tree, the left child contains nodes with values less than the parent node and where the right child only contains nodes with values greater than the parent node. There must be no duplicate nodes. Searching takes O(log n). In a BST with n nodes, moving from one level to the next requires one comparison, and there are log_2(n) levels, for a total of log_2(n) comparisons.

3 ways to traverse a binary tree. Traversal requires O(n) time, since it must visit every node.

  1. In Order
  2. PostOrder
  3. Pre Order

Applications

  1. Searching
  2. Building block for most databases
  3. Many specialized BST's such as RBTree and AVLTree
  4. Syntax Tree used by compilers