Binary Tree & Binary Search Tree

Theory

Traversal

pre-order: root -> left sub-tree -> right sub-tree

in-order: left sub-tree -> root -> right sub-tree

post-order: left sub-tree -> right sub-tree -> root

base case usually refers to the null child node below the leaf node.

Balanced Binary Tree

Is usually defined as a binary tree in which the height of the left and right subtree of every node differ by 1 or less.

• Conclusion: If a balanced binary tree has n nodes, then the height of this tree id O(log_2(n))
  • Caveat: If a tree has n number of nodes, but we don’t know if it is balanced, then the height of the tree is O(n). (the worst case)

Complete Binary Tree

Is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

• Conclusion: If a tree is a complete tree, then it must be a balanced tree. But a balanced tree may not be a complete tree.

Binary Search Tree

For every single node in the tree, the values in its left subtree are all smaller than its value, the values in its right subtree are all larger than its value.

• Conclusion: If we print the value of the node in BST in in-order sequence, then it must form an ascending order.

Tree is a special kind of DAG(directed acyclic graph)

Basic operations of BST

• search() - O(height), worst case O(n), best case O(logn)
• remove() - O(height), worst case O(n), best case O(logn)
• insert() - O(height), worst case O(n), best case O(logn)

1
2
3

Assumptions

There are no duplicate keys in the binary search tree