Understanding Trees
Trees are hierarchical data structures with nodes connected by edges. Each tree has a root node with child nodes, forming a parent-child relationship.
typescript
interface TreeNode<T> {
value: T;
left?: TreeNode<T>;
right?: TreeNode<T>;
}Tree Traversals
Depth-First Traversal
typescript
// In-order: Left, Root, Right
function inorderTraversal<T>(node: TreeNode<T> | undefined): T[] {
if (!node) return [];
return [
...inorderTraversal(node.left),
node.value,
...inorderTraversal(node.right)
];
}
// Pre-order: Root, Left, Right
function preorderTraversal<T>(node: TreeNode<T> | undefined): T[] {
if (!node) return [];
return [
node.value,
...preorderTraversal(node.left),
...preorderTraversal(node.right)
];
}
// Post-order: Left, Right, Root
function postorderTraversal<T>(node: TreeNode<T> | undefined): T[] {
if (!node) return [];
return [
...postorderTraversal(node.left),
...postorderTraversal(node.right),
node.value
];
}Breadth-First Traversal
typescript
function levelOrderTraversal<T>(root: TreeNode<T>): T[][] {
if (!root) return [];
const result: T[][] = [];
const queue: [TreeNode<T>, number][] = [[root, 0]];
while (queue.length > 0) {
const [node, level] = queue.shift()!;
if (!result[level]) result[level] = [];
result[level].push(node.value);
if (node.left) queue.push([node.left, level + 1]);
if (node.right) queue.push([node.right, level + 1]);
}
return result;
}Common Tree Operations
Tree Height
typescript
function treeHeight<T>(node: TreeNode<T> | undefined): number {
if (!node) return 0;
return 1 + Math.max(
treeHeight(node.left),
treeHeight(node.right)
);
}Tree Diameter
typescript
function treeDiameter<T>(root: TreeNode<T>): number {
let maxDiameter = 0;
function height(node: TreeNode<T> | undefined): number {
if (!node) return 0;
const leftHeight = height(node.left);
const rightHeight = height(node.right);
maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
return 1 + Math.max(leftHeight, rightHeight);
}
height(root);
return maxDiameter;
}Lowest Common Ancestor
typescript
function lowestCommonAncestor<T>(
root: TreeNode<T>,
p: T,
q: T
): TreeNode<T> | null {
if (!root) return null;
if (root.value === p || root.value === q) return root;
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
if (left && right) return root;
return left || right;
}Binary Search Trees
BST Operations
typescript
function searchBST<T>(root: TreeNode<T> | undefined, value: T): TreeNode<T> | null {
if (!root) return null;
if (root.value === value) return root;
return value < root.value
? searchBST(root.left, value)
: searchBST(root.right, value);
}
function insertBST<T>(root: TreeNode<T>, value: T): TreeNode<T> {
if (value < root.value) {
if (!root.left) {
root.left = { value };
} else {
insertBST(root.left, value);
}
} else {
if (!root.right) {
root.right = { value };
} else {
insertBST(root.right, value);
}
}
return root;
}Validate BST
typescript
function isValidBST<T>(root: TreeNode<T> | undefined): boolean {
function validate(
node: TreeNode<T> | undefined,
min: T | null,
max: T | null
): boolean {
if (!node) return true;
if (min !== null && node.value <= min) return false;
if (max !== null && node.value >= max) return false;
return (
validate(node.left, min, node.value) &&
validate(node.right, node.value, max)
);
}
return validate(root, null, null);
}Balanced Trees
AVL Tree Rotation
typescript
function rotateRight<T>(y: TreeNode<T>): TreeNode<T> {
const x = y.left!;
const T2 = x.right;
x.right = y;
y.left = T2;
return x;
}Common Problems
Maximum Path Sum
typescript
function maxPathSum(root: TreeNode<number>): number {
let maxSum = -Infinity;
function maxGain(node: TreeNode<number> | undefined): number {
if (!node) return 0;
const leftGain = Math.max(maxGain(node.left), 0);
const rightGain = Math.max(maxGain(node.right), 0);
const newPathSum = node.value + leftGain + rightGain;
maxSum = Math.max(maxSum, newPathSum);
return node.value + Math.max(leftGain, rightGain);
}
maxGain(root);
return maxSum;
}Time Complexity
- Traversal: O(n)
- Search BST: O(log n) average, O(n) worst
- Insert BST: O(log n) average, O(n) worst
- Height: O(n)
Conclusion
Tree algorithms are fundamental. Master traversals, BST operations, and common tree problems for technical interviews.
Practice tree algorithms daily!