Interview Cheat Sheets | Tree Cheat Sheet
December 22nd, 2023
Introduction
This article will serve to further summarize the excellent overview of trees from the tech interview handbook.
Overview:
- A tree is an abstract data type representing a hierarchical structure.
- Trees are undirected, connected, and acyclic graphs used to represent hierarchical relationships in various data structures like file systems, JSON, and HTML documents.
- There are no cycles or loops. Each node can be like the root node of its own subtree, making recursion a useful technique for tree traversal.
- For interviews, binary trees and binary search trees (BST) are commonly discussed.
Common Terms:
- Neighbor - Parent or child of a node
- Ancestor - A node reachable by traversing its parent chain
- Descendant - A node in the node’s subtree
- Degree - Number of children of a node
- Degree of a tree - Maximum degree of nodes in the tree
- Distance - Number of edges along the shortest path between two nodes
- Level/Depth - Number of edges along the unique path between a node and the root node
- Width - Number of nodes in a level
Binary Tree:
- Binary trees consist of nodes with a maximum of two children.
- Complete binary tree - A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.
- Balanced binary tree - A binary tree structure in which the left and right subtrees of every node differ in height by no more than 1.
- Traversals include in-order (Left -> Root -> Right), pre-order (Root -> Left -> Right), and post-order (Left -> Right -> Root).
Binary Search Tree (BST):
- In-order traversal of a BST provides elements in order.
- Properties and validation of a BST are crucial.
Time Complexity:
Operation | Big-O |
---|---|
Access | O(log(n)) |
Search | O(log(n)) |
Insert | O(log(n)) |
Remove | O(log(n)) |
The space complexity of traversing balanced trees is O(h) where h is the height of the tree, while traversing very skewed trees (which is essentially a linked list) will be O(n).
Interview Considerations:
- Emphasis on recursive traversals (pre-order, in-order, post-order) and iterative approaches.
- Handling corner cases: empty tree, single node, two nodes, and skewed tree.
Techniques:
- Recursive approaches are common for tree traversal; base case checks are crucial, usually when a node is
null
. - Level-wise traversal is essential for breadth-first search.
Essential Questions:
-
Binary Tree:
- Maximum Depth of Binary Tree
- Invert/Flip Binary Tree: My solution
-
Binary Search Tree:
- Lowest Common Ancestor of a Binary Search Tree - My solution
Recommended Practice Questions:
- Binary tree
- Same Tree
- Binary Tree Maximum Path Sum
- Binary Tree Level Order Traversal
- Binary Tree Right Side View - My solution
- Subtree of Another Tree
- Construct Binary Tree from Preorder and Inorder Traversal
- Serialize and Deserialize Binary Tree
- Binary search tree
- Validate Binary Search Tree - My solution
- Kth Smallest Element in a BST