Stop 18 · Data Structures & AlgorithmsTopics · 8/17

Tree

Part of the Full Stack Developer Roadmap

In short

Trees are everywhere in backend work: database indexes, file systems, JSON, the DOM. In interviews, nearly every tree question is a tiny recursive function in disguise.

A hierarchical data structure of nodes with parent-child relationships — binary trees and BSTs are a huge, recurring category in interviews.

Think of it like this

A family tree

Dadaji sits at the top. Below him are his children, and below them, the grandchildren. Every person has one parent line going up and any number of children going down. Ask "how many generations?" and you're computing tree height.

Watch it happen

Searching for 6 in a BST

1/3Start at the root, 8. In a binary search tree, smaller values live on the left.

The big ideas

What you need to know

Root, children, leaves

A binary tree node has at most two children. Nodes with no children are leaves.

BST ordering

Left subtree smaller, right subtree bigger. Search, insert and delete are O(log n) if the tree stays balanced.

Three DFS orders

Preorder (node first), inorder (node in the middle) and postorder (node last). Inorder on a BST gives sorted output.

BFS for levels

Use a queue to visit level by level, perfect for "print each level" or "right side view" questions.

See it in code

Walk through the code

1type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };2 3function search(node: TreeNode | null, target: number): TreeNode | null {4  if (!node) return null;                 // fell off the tree5  if (target === node.val) return node;6  return target < node.val7    ? search(node.left, target)           // smaller: go left8    : search(node.right, target);         // bigger: go right9}10 11function maxDepth(node: TreeNode | null): number {12  if (!node) return 0;13  return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));14}

1/3Base cases: an empty spot means not found; a match means done.

Both functions follow the same recipe: handle the empty node, then trust the recursive call to solve each child.

Save yourself the pain

Common mistakes

Oops

Checking only a node's direct children to validate a BST.

Do this instead

Every node in the left subtree must be smaller. Pass down min and max limits as you recurse.

Oops

Assuming a BST is always O(log n).

Do this instead

Insert sorted data and it becomes a straight line, O(n). Balanced trees like B-trees in databases fix this.

Your mission

Tree recursion set

~40 min

Quick check

Which traversal of a binary search tree gives the values in sorted order?

Go deeper

1Implement tree traversals: inorder, preorder, postorder, and level-order (BFS).
2Solve classic problems: max depth, validate a BST, lowest common ancestor.
3Practice both recursive and iterative traversal implementations.