Tree Terminology and Fundamentals

# CHAPTER 2

Tree Terminology and Fundamentals #

1. Introduction #

2. Learning Objectives #

• Identify and define all core nodes within a tree structure (Root, Parent, Child, Leaf).

• Distinguish between internal and external nodes.

• Calculate the Height and Depth of a specific node or an entire tree.

• Understand the concept of Subtrees and node Degrees.

3. Core Node Terminology #

1. Node: The fundamental building block of a tree. It contains data (a value) and links/pointers to other nodes. 2. Root: The absolute top-most node of a tree. It is the only node in the entire tree that has zero parents. Every algorithm begins here. 3. Edge: The physical link connecting two nodes. If a tree has $N$ nodes, it will ALWAYS have exactly $N-1$ edges.

Visual Tree:

        A (Root)
       / \
      B   C
     / \   \
    D   E   F

4. Parent: A node that has an edge pointing downward to a lower node. (e.g., $B$ is the parent of $D$ and $E$). 5. Child: A node directly connected to an upward parent. (e.g., $F$ is the child of $C$). 6. Siblings: Nodes that share the exact same parent. (e.g., $D$ and $E$ are siblings. $B$ and $C$ are siblings).

4. Node Classifications #

• Leaf Node (External Node): A node at the very bottom of the tree that has NO children. (e.g., $D, E,$ and $F$ are leaves).

• Internal Node: Any node that has at least one child. It is not a leaf. (e.g., $A, B,$ and $C$ are internal nodes).

5. Height vs. Depth #

Depth of a Node: The number of edges from the Root straight down to the specific node.

• *Perspective:* Counting from the top down.

• Depth of Root ($A$) = $0$.

• Depth of $B$ = $1$.

• Depth of $D$ = $2$.

Height of a Node: The number of edges on the longest path from the specific node straight down to a Leaf.

• *Perspective:* Counting from the bottom up.

• Height of Leaf ($D$) = $0$.

• Height of $B$ = $1$ (Path: $B \rightarrow D$).

• Height of Root ($A$) = $2$ (Path: $A \rightarrow B \rightarrow D$).

Height of the Tree: The height of the Root node. In our example, the tree has a height of $2$.

6. Subtrees and Degree #

• Subtree: A tree entirely contained within a larger tree. Any child node can be treated as the "Root" of its own localized Subtree. (e.g., Node $B$ and its children $D$ and $E$ form a Subtree of the main tree).

• Degree of a Node: The total number of children a specific node has. (e.g., The degree of $B$ is 2. The degree of $C$ is 1. The degree of $F$ is 0).

7. Step-by-Step Code: Node Structure #

C++:

#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    vector<TreeNode*> children; // Array of pointers to children
    
    TreeNode(int x) {
        val = x;
    }
};

int main() {
    TreeNode* root = new TreeNode(10);
    TreeNode* child1 = new TreeNode(20);
    TreeNode* child2 = new TreeNode(30);
    
    root->children.push_back(child1);
    root->children.push_back(child2);
    
    cout << "Root value: " << root->val << endl;
    cout << "Degree of Root: " << root->children.size() << endl;
    
    return 0;
}

Python:

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.children = [] # List to hold children

root = TreeNode(10)
child1 = TreeNode(20)
child2 = TreeNode(30)

root.children.extend([child1, child2])

print(f"Root value: {root.val}")
print(f"Degree of Root: {len(root.children)}")

8. Complexity Analysis #

• Finding the Depth of a node: $O(H)$ where $H$ is the height of the tree (Traversing upward from the node to the Root).

• Finding the Height of a node: $O(N)$ where $N$ is the number of nodes in that subtree (Requires traversing all downward paths to find the longest one).

9. Common Mistakes #

• Mixing up Height and Depth: Remember: Depth goes Down from the Root. Height goes High (up) from the Leaves.

• Edge Counting vs Node Counting: In modern computer science, Height and Depth are measured by counting the Edges (lines), not the Nodes. A single node tree has a height of 0.

10. Best Practices #

• When analyzing time complexity for tree algorithms, express the worst-case scenario in terms of $O(H)$ (Height of the tree), rather than $O(N)$, as a balanced tree's height is significantly smaller than its node count.

11. Exercises #

1. 1. Draw a tree with 5 nodes. Identify the Root, all Leaf nodes, and the Degree of the Root.

1. 2. Given a straight-line tree ($A \rightarrow B \rightarrow C \rightarrow D$), what is the height of the tree?

12. MCQs with Answers #

13. Interview Questions #

• Q: Given a pointer to a node in a tree, write an algorithm to calculate its Depth. *(Hint: Traverse parent pointers upward until you hit the Root, counting the steps).*

• Q: Can a tree have a node with a degree of 5? *(Answer: Yes, a general tree can have infinite children. Binary trees restrict it to 2).*

14. Summary #

15. Next Chapter Recommendation #