Beginner LevelData Structures & Algorithms
What is a Binary Tree and what are its key properties?
ā Interview Prompt: Define Binary Trees, explain height, depth, balanced vs unbalanced, full vs complete vs perfect binary trees, and traversal types.
A Binary Tree is a hierarchical data structure where each node has at most two children (left and right).
Key Terms:
ā¢
Height: Longest path from root to a leaf node.
ā¢
Depth: Distance from the root to a given node.
ā¢
Full Binary Tree: Every node has 0 or 2 children.
ā¢
Complete Binary Tree: All levels are filled except possibly the last, filled left-to-right.
ā¢
Perfect Binary Tree: All internal nodes have 2 children; all leaves at the same depth.
ā¢
Balanced: Height difference between left and right subtrees ā¤ 1 at every node (AVL, Red-Black Trees).
Traversal Types:
| Traversal | Order | Use Case |
|---|---|---|
| Inorder | Left ā Root ā Right | BST sorted output |
| Preorder | Root ā Left ā Right | Tree serialisation |
| Postorder | Left ā Right ā Root | Directory size calc |
| Level Order | BFS level by level | Shortest path |
Code Implementation Example
typescript
class TreeNode {
val: number;
left: TreeNode | null = null;
right: TreeNode | null = null;
constructor(val: number) { this.val = val; }
}
// Inorder Traversal ā O(N)
function inorder(root: TreeNode | null, result: number[] = []): number[] {
if (!root) return result;
inorder(root.left, result);
result.push(root.val);
inorder(root.right, result);
return result;
}š”Binary Tree node definition and recursive Inorder traversal.
šÆ Interview Key Takeaway
Master all four traversal types (inorder, preorder, postorder, level-order) ā they underpin most tree interview problems.
#DSA#Binary Tree#Traversal#Trees#Beginner
Back to all Data Structures & Algorithms Questionsā