Stop 21 · Data Structures & AlgorithmsTopics · 8/17

Tree

In short

The DOM you've been styling all along is a tree. Tree questions test recursion more than anything else, so once recursion clicks, most of them follow one template.

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

The jaadu stands at the top of an org chart of small friendly figures.

Think of it like this

Your college's org chart

The principal is at the top. Under them are HODs, and under each HOD are professors. Ask 'how many people in total?' and each HOD counts their own team and reports up. Trees work exactly like that.

Watch it happen

maxDepth on a small BST

1/6maxDepth(8) starts. It must ask both children before it can answer.

The big ideas

What you need to know

Root, children, leaves

One root at the top. Each node can have children. Nodes with no children are leaves.

Every subtree is a tree

So most answers are: solve for the left subtree, solve for the right, combine.

BST keeps things ordered

In a Binary Search Tree, left is smaller and right is bigger, so search is O(h), where h is height.

DFS vs BFS

DFS (recursion) goes deep down one branch first. BFS (a queue) goes level by level.

See it in code

Walk through the code

1// node: { val, left, right }2function maxDepth(node) {3  if (!node) return 0;4  const left = maxDepth(node.left);5  const right = maxDepth(node.right);6  return 1 + Math.max(left, right);7}

1/3Base case: an empty spot adds no depth.

Each node is visited once, so time is O(n). Stack space is O(h): O(log n) if balanced, O(n) if the tree is one long chain.

Save yourself the pain

Common mistakes

Oops

Assuming a BST search is always O(log n).

Do this instead

That's only for a balanced tree. Insert sorted data into a plain BST and it becomes a chain with O(n) search.

Oops

Forgetting the null check and crashing on node.left of undefined.

Do this instead

Write the base case first, before anything else in a tree function.

Your mission

Tree trio

~40 min

Quick check

You insert 1, 2, 3, 4, 5 in that order into an empty BST (no balancing). How long does searching for 5 take?

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.