Binary Trees & BST
DSA · Intermediate
Definition
A binary tree is a hierarchy where each node has at most two children. In a Binary Search Tree, left < node < right.
Trees model hierarchies and give O(log n) search when balanced.
Diagram
Flowchart
Example: Inorder traversal (sorted output for BST)
def inorder(node):
if not node: return []
return inorder(node.left) + [node.val] + inorder(node.right)Complexity
Balanced BST search O(log n) · Skewed O(n)
Key points
- Traversals: inorder, preorder, postorder, level-order
- Height decides performance
- AVL/Red-Black keep balance
Interview questions
Max depth of a tree?
1 + max(depth(left), depth(right)), with 0 for null.
Validate a BST?
Pass allowed min/max bounds down while recursing.