DSA — Non-Linear DS

Binary Search Tree

Binary tree where left < parent < right. O(log n) average search, insert, delete.

— min read
O(log n)Search
O(log n)Insert
O(log n)Delete
BSTProperty
BalancedO(log n)
// BINARY SEARCH TREE
Use Insert/Search buttons
How It Works
Python Code
Complexity
Quiz
Practice
01
Insert Rule
Values less than node go left, greater go right.
if val < node.val: go left
02
Search
Follow left/right until found or null — O(log n) avg.
while node: compare and move
03
Inorder = Sorted
Left→Root→Right gives sorted sequence.
04
Balance Matters
Worst case O(n) if tree is skewed (sorted input).
Python — BST Insert & Search 
class BST:
    def insert(self, root, val):
        if not root: return Node(val)
        if   val < root.val: root.left  = self.insert(root.left,  val)
        elif val > root.val: root.right = self.insert(root.right, val)
        return root

    def search(self, root, val):
        if not root or root.val == val: return root
        if val < root.val: return self.search(root.left, val)
        return             self.search(root.right, val)
O(log n)
Search/Insert
Balanced tree — height = log n
O(n)
Worst Case
Skewed tree e.g. sorted input
Inorder
Sorted Output
Left→Root→Right = sorted
O(n)
Space
One node per element
What traversal of a BST gives sorted output?
Progress0 / 13 solved
13 problems · 10 PBC · 3 Startup
#071 Maximum Depth of Binary Tree Amazon, Microsoft PBC →
#072 Validate Binary Search Tree Google, Meta PBC →
#073 Lowest Common Ancestor of BST Apple, Amazon PBC →
#074 Binary Tree Level Order Traversal Microsoft PBC →
#075 Invert Binary Tree Google, Amazon PBC →
#076 Serialize and Deserialize Binary Tree Google, Meta PBC →
#077 Construct Tree from Preorder and Inorder Meta, Amazon PBC →
#078 Path Sum Amazon, Apple PBC →
#079 Symmetric Tree Microsoft PBC →
#080 Subtree of Another Tree Google, Meta PBC →
#082 Right View of Binary Tree Meesho STARTUP →
#086 Zigzag Level Order Traversal Zepto STARTUP →
#088 Flatten Binary Tree to Linked List Meesho STARTUP →
← Queue & Deque