Binary tree terminology in Data Structures Theory - Mini Project: Build & Apply

Binary Tree Terminology

📖 Scenario: You are learning about binary trees, a common way to organize data in computer science. Understanding the basic terms helps you describe and work with these trees clearly.

🎯 Goal: Build a simple representation of a binary tree using a dictionary to understand key terms like root, parent, child, leaf, and subtree.

📋 What You'll Learn

Create a dictionary representing nodes and their children

Add a variable to identify the root node

Use a loop to list all leaf nodes

Add a final statement describing the subtree of a specific node

💡 Why This Matters

🌍 Real World

Binary trees are used in many areas like organizing data for quick search, sorting, and managing hierarchical information such as file systems.

💼 Career

Understanding binary tree terminology is essential for software developers, data scientists, and anyone working with algorithms or data structures.

1

Create the binary tree structure

Create a dictionary called binary_tree with these exact entries: 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F', 'G'], 'D': [], 'E': [], 'F': [], 'G': []. This represents each node and its children.

Data Structures Theory

# Create the binary_tree dictionary with nodes and their children
# Your code here

Hint

Think of each key as a node and the list as its children nodes.

2

Identify the root node

Create a variable called root and set it to the string 'A', which is the root node of the binary tree.

Data Structures Theory

binary_tree = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': [],
    'E': [],
    'F': [],
    'G': []
}
# Set the root node
# Your code here

Hint

The root is the top node with no parent, here it is 'A'.

3

List all leaf nodes

Create a list called leaves that contains all nodes from binary_tree whose children list is empty. Use a for loop with variables node and children to iterate over binary_tree.items().

Data Structures Theory

binary_tree = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': [],
    'E': [],
    'F': [],
    'G': []
}
root = 'A'
# Create leaves list using a for loop
# Your code here

Hint

Leaf nodes have no children, so their children list is empty.

4

Describe the subtree of node 'B'

Create a variable called subtree_B and set it to the list of children of node 'B' from binary_tree. This represents the subtree rooted at node 'B'.

Data Structures Theory

binary_tree = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': [],
    'E': [],
    'F': [],
    'G': []
}
root = 'A'
leaves = []
for node, children in binary_tree.items():
    if children == []:
        leaves.append(node)
# Set subtree_B to children of 'B'
# Your code here

Hint

The subtree of a node includes its children. Here, get the children of 'B'.

Practice

1. In a binary tree, what do we call the topmost node that has no parent?

easy

A. Root

B. Leaf

C. Internal node

D. Child

Solution

1. Step 1: Understand the position of nodes in a binary tree

   The topmost node in a binary tree is the starting point and has no parent node above it.

2. Step 2: Identify the term for the topmost node

   This node is called the root because it is the base from which all other nodes branch out.

3. Final Answer:

   Root -> Option A

4. Quick Check:

   Top node = Root [OK]

Hint: Top node with no parent is always the root [OK]

Common Mistakes:

• Confusing root with leaf
• Thinking root has a parent
• Calling root a child

2. Which of the following correctly describes a leaf node in a binary tree?

easy

A. The topmost node

B. A node with exactly two children

C. A node with one child

D. A node with no children

Solution

1. Step 1: Recall the definition of a leaf node

   A leaf node is a node that does not have any children, meaning it is at the end of a branch.

2. Step 2: Match the definition with the options

   A node with no children states the node has no children, which matches the leaf node definition.

3. Final Answer:

   A node with no children -> Option D

4. Quick Check:

   Leaf node = no children [OK]

Hint: Leaf nodes have zero children, no branches below [OK]

Common Mistakes:

• Thinking leaf has children
• Confusing leaf with root
• Assuming leaf has one child

3. Consider this binary tree node description:
Node A has two children: Node B (left) and Node C (right). Node B has no children. Node C has one child: Node D (left).
Which of these nodes is an internal node?

medium

A. Node B only

B. Node D only

C. Node A and Node C

D. Node A only

Solution

1. Step 1: Define internal nodes

   Internal nodes have at least one child. Leaf nodes have none.

2. Step 2: Analyze each node's children

   Node A has two children (B and C), so it is internal. Node B has no children, so it is a leaf. Node C has one child (D), so it is internal. Node D has no children, so it is a leaf.

3. Final Answer:

   Node A and Node C -> Option C

4. Quick Check:

   Internal nodes = nodes with children [OK]

Hint: Internal nodes have one or two children, leaves have none [OK]

Common Mistakes:

• Calling leaf nodes internal
• Ignoring nodes with one child
• Confusing node labels

4. Identify the error in this statement about binary trees:
"A leaf node can have one child."

medium

A. Leaf nodes cannot have any children, so the statement is false.

B. Leaf nodes are always the root, so the statement is false.

C. Leaf nodes can have two children, so the statement is false.

D. Leaf nodes must have exactly one child, so the statement is true.

Solution

1. Step 1: Recall the definition of a leaf node

   A leaf node is defined as a node with no children at all.

2. Step 2: Evaluate the statement

   The statement says a leaf node can have one child, which contradicts the definition. Therefore, the statement is false.

3. Final Answer:

   Leaf nodes cannot have any children, so the statement is false. -> Option A

4. Quick Check:

   Leaf node = no children [OK]

Hint: Leaf nodes have zero children, never one [OK]

Common Mistakes:

• Thinking leaf can have children
• Confusing leaf with internal node
• Misunderstanding node roles

5. You have a binary tree where every internal node has exactly two children, and all leaves are at the same depth. What is this type of binary tree called?

hard

A. Complete binary tree

B. Perfect binary tree

C. Balanced binary tree

D. Full binary tree

Solution

1. Step 1: Understand the definitions of binary tree types

   A full binary tree has every node with 0 or 2 children. A complete binary tree is filled level by level left to right. A balanced binary tree has heights of subtrees differ by at most one. A perfect binary tree is full and all leaves are at the same depth.

2. Step 2: Match the given conditions

   The tree described has every internal node with exactly two children (full) and all leaves at the same depth, which matches the perfect binary tree definition.

3. Final Answer:

   Perfect binary tree -> Option B

4. Quick Check:

   Full + all leaves same depth = Perfect tree [OK]

Hint: Full + all leaves same depth = Perfect binary tree [OK]

Common Mistakes:

• Confusing complete with perfect
• Mixing balanced with perfect
• Ignoring leaf depth condition