15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A tree is a connected hierarchy of nodes joined by edges. One node is the root and has no parent. Every other node has exactly one parent, so following parent links always reaches the root. A binary tree limits each node to at most two children, a left and a right.
| Root | The one node with no parent, at depth 0 |
|---|---|
| Depth of a node | Edges on the path from the root to that node |
| Leaf and internal node | A leaf has no children; an internal node has at least one |
| Binary tree | At most two children per node, a left and a right |
| Time to find a node's depth | O(d) by following parent links, O(1) extra space |
A tree is a connected hierarchy of nodes joined by edges.
The lesson uses a rooted tree. One node is chosen as the root. The root has no parent. Every other node has exactly one parent.
We use these conventions:
A general rooted tree allows a node to have zero or more children. A binary tree limits each node to at most two children:
Those names describe positions. They do not specify node-value ordering.
For terminology and structure, use these references:
Start with these relationships:
1A is the root
2A.left = B
3A.right = C
4B.left = D
5B.right = EDraw the nodes before attaching any child links:
1A
2
3B C
4
5D ENow connect them:
1 A
2 / \
3 B C
4 / \
5 D EA is the root.A is the parent of B and C.B is the parent of D and E.B and C are siblings.D and E are siblings.A and B are internal nodes.C, D, and E are leaves.A has depth 0.B and C have depth 1.D and E have depth 2.For node E:
B.B, then A.E, because E has no children.B contains B, D, and E.A binary tree does not require every internal node to have two children. “Binary” means at most two children.
For example, this is still a valid binary tree:
1 A
2 /
3 BA is internal because it has one child. B is a leaf. The missing right child is allowed.
Build the example one child link at a time.
Create A with no parent.
1AA is the root, so its depth is 0.
At this point, A has no children. It is temporarily a leaf.
Set A.left = B.
The example tree grows one child link at a time: A, then B and C below A, then D and E below B. Depths are 0, 1 and 2.
Now set B.parent = A.
B has exactly one parent. A has one left child.
Next set A.right = C.
Now set C.parent = A.
B and C share parent A, so they are siblings. Both have depth 1.
A is now internal. B and C are leaves for the moment.
Set B.left = D, then set D.parent = B.
Next set B.right = E, then set E.parent = B.
D and E have depth 2. They are siblings because both have parent B.
Look at each node’s child links.
| Node | Left child | Right child | Classification |
|---|---|---|---|
| A | B | C | Internal |
| B | D | E | Internal |
| C | none | none | Leaf |
| D | none | none | Leaf |
| E | none | none | Leaf |
Start at E.
1E.parent = B
2B.parent = A
3A.parent = noneSo:
E: BE: B, then AE: 2, because the path A → B → E has two edges.The subtree rooted at B is:
1 B
2 / \
3 D EIt contains B, D, and E. It does not contain A or C.
After each valid attachment, the structure must still behave like a rooted tree.
A remains the one root.A.The invariant is:
In a rooted tree, every node except the root has exactly one parent, and following parent links from any node eventually reaches the root without revisiting a node.
For the example:
1E → B → A → no parent
2D → B → A → no parent
3C → A → no parentEach upward path ends at A. None repeats a node.
The left and right links have one more rule in a binary tree:
1node.left is either one child or empty
2node.right is either one child or emptyA node may have:
It may not have a third child.
Use a construction procedure that preserves the tree rules whenever it attaches a child.
Suppose we want to attach child below parent.
Before changing links, check these conditions:
left or right.parent is empty.child does not already have a parent.child is not the root.For the lesson’s example, every child is new when attached, so conditions 2 through 5 hold.
The link change has two parts:
1parent.left or parent.right = child
2child.parent = parentBoth links matter.
Once the tree exists, depth follows from the parent links:
depth = 0.1 each time.For E, this is:
1E → B depth becomes 1
2B → A depth becomes 2
3A has no parent, stopThe pseudocode uses nodes with these fields:
1Node:
2 value
3 left // Node or null
4 right // Node or null
5 parent // Node or nullAttachChild mutates the two supplied nodes. It returns success or failure.
11 function AttachChild(parent, child, side) -> boolean
22 // Mutates parent and child only when it returns true.
33 // side must be "left" or "right".
44
55 if parent is null or child is null:
66 return false
77
88 if side is not "left" and side is not "right":
99 return false
1010
1111 if child.parent is not null:
1212 return false
1313
1414 if side = "left" and parent.left is not null:
1515 return false
1616
1717 if side = "right" and parent.right is not null:
1818 return false
1919
2020 current = parent
2121 while current is not null:
2222 if current = child:
2323 return false
2424 current = current.parent
2525
2626 if side = "left":
2727 parent.left = child
2828 else:
2929 parent.right = child
3030
3131 child.parent = parent
3232 return trueLines 20 through 24 prevent a cycle. If child were already an ancestor of parent, attaching it below parent would create a loop.
The following procedure builds the exact board example. It returns the root. It mutates the newly created nodes.
11 function BuildExampleTree() -> Node
22 A = new Node("A")
33 B = new Node("B")
44 C = new Node("C")
55 D = new Node("D")
66 E = new Node("E")
77
88 A.parent = null
99
1010 AttachChild(A, B, "left")
1111 AttachChild(A, C, "right")
1212 AttachChild(B, D, "left")
1313 AttachChild(B, E, "right")
1414
1515 return ATo find a node’s depth when the node is already referenced:
11 function Depth(node) -> integer or null
22 // Does not mutate the tree.
33 // Returns null when node is null.
44
55 if node is null:
66 return null
77
88 depth = 0
99 current = node
1010
1111 while current.parent is not null:
1212 current = current.parent
1313 depth = depth + 1
1414
1515 return depthA node is a leaf exactly when both child positions are empty:
11 function IsLeaf(node) -> boolean
22 // Does not mutate the tree.
33
44 if node is null:
55 return false
66
77 return node.left is null and node.right is nullRun BuildExampleTree().
| Pseudocode line | State |
|---|---|
| 2 | Create A. Its left, right, and parent links are empty. |
| 3 | Create B with empty links. |
| 4 | Create C with empty links. |
| 5 | Create D with empty links. |
| 6 | Create E with empty links. |
| 8 | Set A.parent = null. A is the root. |
| 10 | Call AttachChild(A, B, "left"). B.parent is empty and A.left is empty. Set A.left = B, then B.parent = A. |
| 11 | Call AttachChild(A, C, "right"). C.parent is empty and A.right is empty. Set A.right = C, then C.parent = A. |
| 12 | Call AttachChild(B, D, "left"). D.parent is empty and B.left is empty. Set B.left = D, then D.parent = B. |
| 13 | Call AttachChild(B, E, "right"). E.parent is empty and B.right is empty. Set B.right = E, then E.parent = B. |
| 15 | Return A. |
The returned tree is:
1 A
2 / \
3 B C
4 / \
5 D ENow run Depth(E).
| Pseudocode line | current | depth | Explanation |
|---|---|---|---|
| 8–9 | E | 0 | Start at E. |
| 11–13, first pass | B | 1 | E has parent B. Move across one edge. |
| 11–13, second pass | A | 2 | B has parent A. Move across one edge. |
| 11 | A | 2 | A has no parent, so stop. |
| 15 | — | 2 | Return 2. |
Run IsLeaf(E).
1E.left = null
2E.right = nullThe result is true.
Run IsLeaf(B).
1B.left = D
2B.right = EThe result is false.
Prove correctness by considering the initial structure, one attachment, and the completed sequence.
Initialization
Before any attachment:
A.parent is null.A is the only root.The rooted-tree condition holds for the tree containing only A.
Preservation
Consider one successful call to AttachChild(parent, child, side).
parent upward. If child appears on that path, the function rejects the attachment. Therefore it does not make an ancestor into a descendant and does not create a cycle.After a successful attachment, the new child has exactly one parent, existing parent links remain unchanged, and all parent chains still reach the root without repetition.
Termination
BuildExampleTree performs four attachment calls:
A to BA to CB to DB to EEach call has finite checks and completes. After the fourth call, the tree has one root, A, and every other node has exactly one parent. The returned node is the root of the stated tree.
Depth returns the correct depthDepth(node) starts with depth 0 at the given node.
Each loop iteration follows exactly one parent link. That moves across exactly one edge toward the root and increases depth by one.
The tree invariant guarantees that parent links cannot cycle and eventually reach the root. When the loop stops, the algorithm has crossed every edge on the unique path from the original node to the root. The returned count is the node’s depth.
If a node is already referenced:
parent link.left and right links.Reading those direct links uses a constant number of operations.
1parent lookup: O(1)
2left/right child lookup: O(1)
3leaf test: O(1)For a node at depth d, Depth follows one parent link per edge on the path to the root.
For E, depth is 2, so the procedure follows:
1E → B
2B → AThat is two parent-link traversals.
In general, the work is proportional to d:
1time: O(d)
2auxiliary space: O(1)The procedure uses current and depth, regardless of tree size.
If we label each node’s depth and whether it is a leaf, we inspect each of the n nodes once.
1time: O(n)A recursive depth-first labeling pass follows one root-to-leaf path at a time. If tree height is h, its recursion stack holds at most h active calls:
1auxiliary space: O(h)An iterative depth-first traversal can use an explicit stack that also holds up to O(h) nodes in this form of processing.
Incorrect assumption:
1A binary-tree node is internal only if it has both a left and a right child.Smallest exposing input:
1 A
2 /
3 BWrong result:
1Declare the structure invalid because A has no right child.Correction:
1A binary-tree node may have zero, one, or two children.
2A is internal because it has at least one child.
3B is a leaf because it has none.Incorrect initialization:
1depth = 1Smallest exposing input:
1AWrong result:
1Depth(A) = 1Correction:
1depth = 0The root is zero edges away from itself.
Incorrect assumption:
1C is an ancestor of E because both are below A.Exposing input:
1 A
2 / \
3 B C
4 /
5 EWrong result:
1Ancestors of E: B, C, ACorrection:
Follow only E’s parent chain:
1E → B → ASo B and A are ancestors of E. C is not.
Incorrect attachment logic:
1parent.left = child
2child.parent = parentwith no check that child.parent is empty.
Exposing input:
1A.left = B
2A.right = C
3B.left = D
4C.left = DWrong state:
1D has links from both B and C.D no longer has one unique path upward. Its parent field can store only one parent, while the downward links claim two parents.
Correction:
Reject the second attachment because D.parent is already set after B.left = D.
| Input | Expected classification or result |
|---|---|
| Empty tree | No root exists. There is no node to classify. |
[A] | A is both root and leaf. Depth(A) = 0. |
A → B as A’s left child | A is internal. B is a leaf. A’s missing right child is valid. |
| D proposed as child of both B and C | Reject the structure because D would have two parents. |
Executable objective: Given a JSON-described rooted binary tree and a target node value, return:
null for the root,The tests check this contract on:
Use the same conventions from the lesson:
0,1class Node:
2 def __init__(self, value):
3 self.value = value
4 self.left = self.right = self.parent = None
5
6def attach_child(parent, child, side):
7 if child.parent is not None: # one parent only
8 return False
9 if getattr(parent, side) is not None: # slot must be empty
10 return False
11 cur = parent
12 while cur is not None: # child must not be an ancestor
13 if cur is child:
14 return False
15 cur = cur.parent
16 setattr(parent, side, child)
17 child.parent = parent
18 return True
19
20def depth(node):
21 d = 0
22 while node.parent is not None:
23 node = node.parent
24 d += 1
25 return d
26
27def leaves(node):
28 if node is None:
29 return []
30 if node.left is None and node.right is None:
31 return [node.value]
32 return leaves(node.left) + leaves(node.right)
33
34a, b, c, d, e = (Node(v) for v in "ABCDE")
35attach_child(a, b, "left")
36attach_child(a, c, "right")
37attach_child(b, d, "left")
38attach_child(b, e, "right")
39
40anc, cur = [], e.parent
41while cur is not None:
42 anc.append(cur.value)
43 cur = cur.parent
44
45print("depth(E) =", depth(e))
46print("parent(E) =", e.parent.value)
47print("ancestors(E) =", " ".join(anc))
48print("leaves =", " ".join(leaves(a)))1import java.util.ArrayList;
2import java.util.List;
3
4public class Main {
5 static class Node {
6 String value;
7 Node left, right, parent;
8 Node(String value) { this.value = value; }
9 }
10
11 static boolean attachChild(Node parent, Node child, String side) {
12 if (child.parent != null) return false; // one parent only
13 if (side.equals("left") ? parent.left != null : parent.right != null) return false;
14 for (Node cur = parent; cur != null; cur = cur.parent) { // child must not be an ancestor
15 if (cur == child) return false;
16 }
17 if (side.equals("left")) parent.left = child; else parent.right = child;
18 child.parent = parent;
19 return true;
20 }
21
22 static int depth(Node node) {
23 int d = 0;
24 while (node.parent != null) {
25 node = node.parent;
26 d++;
27 }
28 return d;
29 }
30
31 static void leaves(Node node, List<String> out) {
32 if (node == null) return;
33 if (node.left == null && node.right == null) out.add(node.value);
34 leaves(node.left, out);
35 leaves(node.right, out);
36 }
37
38 public static void main(String[] args) {
39 Node a = new Node("A"), b = new Node("B"), c = new Node("C");
40 Node d = new Node("D"), e = new Node("E");
41 attachChild(a, b, "left");
42 attachChild(a, c, "right");
43 attachChild(b, d, "left");
44 attachChild(b, e, "right");
45
46 List<String> anc = new ArrayList<>();
47 for (Node cur = e.parent; cur != null; cur = cur.parent) anc.add(cur.value);
48 List<String> leafList = new ArrayList<>();
49 leaves(a, leafList);
50
51 System.out.println("depth(E) = " + depth(e));
52 System.out.println("parent(E) = " + e.parent.value);
53 System.out.println("ancestors(E) = " + String.join(" ", anc));
54 System.out.println("leaves = " + String.join(" ", leafList));
55 }
56}1#include <iostream>
2#include <string>
3#include <vector>
4using namespace std;
5
6struct Node {
7 string value;
8 Node *left = nullptr, *right = nullptr, *parent = nullptr;
9 Node(string v) : value(v) {}
10};
11
12bool attachChild(Node* parent, Node* child, const string& side) {
13 if (child->parent) return false; // one parent only
14 if (side == "left" ? parent->left != nullptr : parent->right != nullptr) return false;
15 for (Node* cur = parent; cur; cur = cur->parent) // child must not be an ancestor
16 if (cur == child) return false;
17 (side == "left" ? parent->left : parent->right) = child;
18 child->parent = parent;
19 return true;
20}
21
22int depth(Node* node) {
23 int d = 0;
24 while (node->parent) {
25 node = node->parent;
26 d++;
27 }
28 return d;
29}
30
31void leaves(Node* node, vector<string>& out) {
32 if (!node) return;
33 if (!node->left && !node->right) out.push_back(node->value);
34 leaves(node->left, out);
35 leaves(node->right, out);
36}
37
38string join(const vector<string>& v) {
39 string s;
40 for (size_t i = 0; i < v.size(); i++) s += (i ? " " : "") + v[i];
41 return s;
42}
43
44int main() {
45 Node a("A"), b("B"), c("C"), d("D"), e("E");
46 attachChild(&a, &b, "left");
47 attachChild(&a, &c, "right");
48 attachChild(&b, &d, "left");
49 attachChild(&b, &e, "right");
50
51 vector<string> anc, leafList;
52 for (Node* cur = e.parent; cur; cur = cur->parent) anc.push_back(cur->value);
53 leaves(&a, leafList);
54
55 cout << "depth(E) = " << depth(&e) << endl;
56 cout << "parent(E) = " << e.parent->value << endl;
57 cout << "ancestors(E) = " << join(anc) << endl;
58 cout << "leaves = " << join(leafList) << endl;
59}1class Node {
2 constructor(value) {
3 this.value = value;
4 this.left = this.right = this.parent = null;
5 }
6}
7
8function attachChild(parent, child, side) {
9 if (child.parent !== null) return false; // one parent only
10 if (parent[side] !== null) return false; // slot must be empty
11 for (let cur = parent; cur !== null; cur = cur.parent) {
12 if (cur === child) return false; // child must not be an ancestor
13 }
14 parent[side] = child;
15 child.parent = parent;
16 return true;
17}
18
19function depth(node) {
20 let d = 0;
21 while (node.parent !== null) {
22 node = node.parent;
23 d++;
24 }
25 return d;
26}
27
28function leaves(node) {
29 if (node === null) return [];
30 if (node.left === null && node.right === null) return [node.value];
31 return [...leaves(node.left), ...leaves(node.right)];
32}
33
34const [a, b, c, d, e] = [...'ABCDE'].map((v) => new Node(v));
35attachChild(a, b, 'left');
36attachChild(a, c, 'right');
37attachChild(b, d, 'left');
38attachChild(b, e, 'right');
39
40const anc = [];
41for (let cur = e.parent; cur !== null; cur = cur.parent) anc.push(cur.value);
42
43console.log(`depth(E) = ${depth(e)}`);
44console.log(`parent(E) = ${e.parent.value}`);
45console.log(`ancestors(E) = ${anc.join(' ')}`);
46console.log(`leaves = ${leaves(a).join(' ')}`);A tree is a hierarchical, non-linear data structure. Each node can lead to several children, so the nodes do not sit in one line the way array or linked list items do.
A tree is a connected graph with no cycles. In the rooted form used here, every node except the root has exactly one parent. A general graph may have cycles and nodes with many incoming edges.
No. Binary means at most two children. A node with only a left child is still internal, and its missing right child is allowed.
Depth is the number of edges from the root to a node. A level is the set of all nodes with the same depth. The root has depth 0, so it sits alone on level 0.
Depth counts edges from the root down to a node. Height counts edges from a node down to its deepest leaf. In the example, E has depth 2 and height 0, while A has depth 0 and height 2.