Intuition The big pictureA tree is a way to organize data that branches out like a family tree or a company org chart — one boss at top, employees below, sub-employees below them, and no loops (you never report to your own subordinate). The vocabulary below is just precise names for "who is where" in that hierarchy. Once these names click, every tree algorithm becomes readable.
A tree is a collection of nodes connected by edges such that:
there is exactly one special node called the root ,
every other node has exactly one parent ,
there are no cycles (no path loops back on itself).
A tree with n n n = = n − 1 = = ==n-1== == n − 1 ==
WHY n − 1 n-1 n − 1 Every node except the root is connected to its parent by exactly one edge. That's n − 1 n-1 n − 1 n − 1 n-1 n − 1 derived , not memorized.
Root ::: the single topmost node, the only one with no parent .Leaf (external node) ::: a node with no children .Internal node ::: a node with at least one child (everything that is not a leaf).Parent / Child ::: if edge goes from A A A B B B A A A B B B Siblings ::: nodes that share the same parent .Ancestor ::: any node on the path from a node up to the root.Descendant ::: any node below a given node.Degree of a node ::: the number of children it has.Degree of a tree ::: the maximum degree of any node in it.Subtree ::: a node plus all its descendants , treated as a tree on its own.
Intuition WHY two different measures?Depth answers "how far am I from the boss (root) ?" — you measure looking up .
Height answers "how far is the deepest worker below me ?" — you measure looking down .
They are mirror questions, so people swap them. Keep them straight by the direction of the arrow.
Definition Depth and Height
Depth of node v v v ::: number of edges on the path from the root down to v v v = = 0 = = ==0== == 0 == Height of node v v v ::: number of edges on the longest path from v v v leaf .
Every leaf has height = = 0 = = ==0== == 0 == Height of the tree ::: the height of its root (= the max depth of any node).
Worked example Example tree A <- depth 0
/ | \
B C D <- depth 1
/ \ \
E F G <- depth 2
\
H <- depth 3
Q: Root? → A. Why this step? It's the only node with no parent.
Q: Leaves? → E, F, C, H. Why? They have no children. (Note C is a leaf even at depth 1 — leaf ≠ deepest!)
Q: Degree of A? → 3 (children B, C, D). Degree of the tree? → 3 (A has the max).
Q: Depth of H? → 3. Why? Path A→D→G→H has 3 edges.
Q: Height of D? → 2. Why? Longest path down: D→G→H = 2 edges.
Q: Height of the tree? → 3 (= height of root A, the longest root-to-leaf path A→D→G→H).
Q: Subtree rooted at D? → nodes {D, G, H} with D as its local root.
Worked example Compute height recursively (Feynman the algorithm)Apply height ( v ) = 1 + max ( children heights ) \text{height}(v) = 1 + \max(\text{children heights}) height ( v ) = 1 + max ( children heights )
h ( E ) = h ( F ) = h ( C ) = h ( H ) = 0 h(E)=h(F)=h(C)=h(H)=0 h ( E ) = h ( F ) = h ( C ) = h ( H ) = 0 Why? No children.h ( G ) = 1 + h ( H ) = 1 h(G) = 1 + h(H) = 1 h ( G ) = 1 + h ( H ) = 1 Why? G's only child H has height 0.h ( B ) = 1 + max ( h ( E ) , h ( F ) ) = 1 + 0 = 1 h(B) = 1 + \max(h(E),h(F)) = 1 + 0 = 1 h ( B ) = 1 + max ( h ( E ) , h ( F )) = 1 + 0 = 1 h ( D ) = 1 + h ( G ) = 1 + 1 = 2 h(D) = 1 + h(G) = 1 + 1 = 2 h ( D ) = 1 + h ( G ) = 1 + 1 = 2 h ( A ) = 1 + max ( h ( B ) , h ( C ) , h ( D ) ) = 1 + max ( 1 , 0 , 2 ) = 3 h(A) = 1 + \max(h(B),h(C),h(D)) = 1 + \max(1,0,2) = 3 h ( A ) = 1 + max ( h ( B ) , h ( C ) , h ( D )) = 1 + max ( 1 , 0 , 2 ) = 3
Common mistake "A leaf must be at the bottom level."Why it feels right: leaves often sit at the deepest level in nice balanced trees, so the brain ties "leaf" to "deepest."
The fix: A leaf is defined only by having no children . In the example, C is a leaf at depth 1 while H is a leaf at depth 3. Leaf = no kids, full stop.
Common mistake "Height and depth are the same number."Why it feels right: for the root , height of tree = max depth, so they coincide there.
The fix: They measure opposite directions. Depth counts up to root ; height counts down to deepest leaf . For a generic node they differ.
Common mistake "Root has depth 1" / "Leaf has height 1."Why it feels right: we naturally start counting at 1.
The fix: We count edges , not nodes. Root: 0 edges to itself → depth 0. Leaf: 0 edges below → height 0. (Some textbooks count nodes; always state your convention . This note uses the edge convention.)
Common mistake "Degree means the number of edges touching a node (like graphs)."Why it feels right: in graph theory degree = total incident edges.
The fix: In trees , degree usually = number of children (downward edges only), ignoring the parent edge.
Recall Explain it to a 12-year-old (hidden)Imagine a family tree drawn upside-down. The great-grandparent at the very top is the root . People with no kids are leaves . Your depth is how many steps up it takes to reach the top boss. Your height is how many steps down to the farthest kid in your branch. Degree is just how many direct children you have. A subtree is "you and your whole family line below you" — it's a little tree all by itself. No one can be their own ancestor, so there are no loops!
D epth → D own from the root (count from top). Root = 0.H eight → H ow far to the bottom leaf. Leaf = 0."Leaf = Leave-less " (no children leave from it).
"Tree degree = the bossiest node's child-count."
A tree with n n n n − 1 n-1 n − 1 ; every node except the root contributes exactly one edge to its parent.
Definition of a leaf? A node with no children.
Definition of root? The single node with no parent; the topmost node.
What is the depth of the root? 0 (zero edges from root to itself).
What is the height of a leaf? 0 (zero edges from it down to a leaf — itself).
Depth vs height, in one line each? Depth = edges up to root; Height = edges down to deepest leaf.
Recursive formula for height of node v? height ( v ) = 1 + max c height ( c ) \text{height}(v) = 1 + \max_{c}\text{height}(c) height ( v ) = 1 + max c height ( c ) , with leaf height
= 0 =0 = 0 .
Degree of a node vs degree of a tree? Node degree = number of its children; tree degree = max degree over all nodes.
What is a subtree? A node together with all its descendants, viewed as a tree on its own.
Can a leaf appear above the bottom level? Yes — leaf means "no children", which can happen at any depth.
Max nodes in a tree of height h with degree ≤ d (d≥2)? d h + 1 − 1 d − 1 \frac{d^{h+1}-1}{d-1} d − 1 d h + 1 − 1 , summing
d 0 + ⋯ + d h d^0+\dots+d^h d 0 + ⋯ + d h .
Height of the whole tree equals? Height of the root = max depth among all nodes.
Binary Trees — special case where degree of tree ≤ 2 \le 2 ≤ 2 Binary Search Trees — ordering invariant built on this terminology.Tree Traversals — DFS/BFS visit nodes by depth/level.Balanced Trees (AVL, Red-Black) — control height to keep operations O ( log n ) O(\log n) O ( log n ) Recursion — height/subtree definitions are inherently recursive.Graphs — a tree is a connected acyclic graph; compare degree definitions.
Intuition Hinglish mein samjhoSocho ek ulta family tree — sabse upar dada ji (jiske upar koi nahi), woh hai root . Jin logon ke koi bacche nahi hai, woh leaf kehlate hain. Tree mein koi loop nahi hota, aur har node ka sirf ek hi parent hota hai. Bas isi structure ke alag-alag hisson ko naam diye gaye hain — yeh terminology hi aage saare tree algorithms ki bhasha ban jaati hai.
Sabse zyada confusion depth aur height mein hota hai. Depth matlab "main root se kitna neeche hoon" — upar ki taraf gin ke, root ki depth 0. Height matlab "mere neeche sabse door wala leaf kitni door hai" — neeche ki taraf gin ke, leaf ki height 0. Yeh dono ulti directions hain, isiliye log galti karte hain. Yaad rakho: Depth = Down from root, Height = how far to the bottom.
Degree ka matlab tree mein hota hai kisi node ke kitne children hain (graph theory wala total edges nahi). Pure tree ka degree = sabse zyada children wale node ka count. Aur subtree matlab koi node plus uske neeche ke saare descendants — woh khud ek chhota tree ban jaata hai, isiliye recursion yahan natural fit hai.
Yeh basics kyun important? Kyunki balanced trees (AVL, Red-Black) ka pura khel height ko control karne ka hai taaki search O ( log n ) O(\log n) O ( log n )
