What is a tree?
A tree is a hierarchy of nodes connected by edges. Exactly one node is the root. Every other node has one parent. There are no cycles — follow child links and you never loop back. Think of a family tree or a file folder nesting: one top, branching down.
- Root
- The top node — the only one with no parent
- Child
- A node reached by an edge from its parent
- Leaf
- A node with no children
- Edge
- The link between a parent and a child
- Height / Depth
- Height is the longest path down from a node; depth is how far a node sits from the root
See it grow
Start at the root. Each node can sprout left and right children. Leaves sit at the tips — nowhere further to go.
Watch the highlight walk root → children, then a new leaf grows on an open edge. That is how trees expand: one link at a time.
Hierarchy, not a flat row — you follow edges, not indexes.
Types of trees
Interviews usually mean a binary tree (at most two children). A binary search tree adds an ordering rule. N-ary trees allow many children. Balanced trees keep height near log n so walks stay fast.
The catalog below is a map of those flavors — same idea, different constraints.
Binary is the interview default. BST adds the sort rule. Balance keeps height short.
How it is stored in memory
In TypeScript the variable root lives on the call stack as a reference.
Each node is an object on the heap with val, left, and right
— those child fields are more references, not nested arrays in one block.
Start here. Each step highlights the TypeScript below.
Operations
Same small tree for each demo. Tap Next to watch inserts, searches, and walks. For copy-paste snippets, open the Functions tab.
BST insert
Compare with the current node. Go left if smaller, right if larger, until you find an empty child slot — hang the new leaf there.
Insert 7 into this BST. Start at the root.
BST search
Same compare walk as insert, but you stop when the value matches — or when you hit null (not found).
Looking for 6. Begin at the root.
DFS preorder
Visit the node first, then recurse left, then right. Useful when the parent must run before its children.
Preorder: visit 8 first (root).
BFS level-order
Use a queue. Drain one level at a time so siblings are visited before deeper descendants.
Queue starts with the root. Visit 8.
Height
Recurse into both subtrees, take the taller side, add one. Empty child counts as height −1 so a lone root is 0.
Height asks: how many edges on the longest path down?