Binary Tree Node Structure in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this binary tree traversal?

Consider the following binary tree node structure and code that creates a simple tree and prints its in-order traversal. What will be printed?

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def inorder(root):
    if root is None:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(3)
root.left.right = Node(7)

print(inorder(root))

A [3, 5, 7, 10, 15]

B [10, 5, 3, 7, 15]

C [3, 7, 5, 10, 15]

D [15, 10, 7, 5, 3]

💡 Hint

In-order traversal visits left child, then node, then right child.

In-order traversal of a binary tree visits nodes in ascending order for a binary search tree. The left subtree nodes (3, 5, 7) come first, then root (10), then right subtree (15).

🧠 Conceptual

intermediate

What does the 'left' attribute in a binary tree node represent?

In a binary tree node structure, what does the 'left' attribute usually represent?

A The value stored in the node

B A reference to the node's left child node

C The parent node of the current node

D The right child node of the current node

💡 Hint

Think about the direction 'left' in a tree structure.

The 'left' attribute points to the node's left child, which is the subtree or node connected on the left side.

❓ Predict Output

advanced

What error does this binary tree node code raise?

What error will this code raise when executed?

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

root = Node(1)
print(root.left.val)

A No error, prints None

B TypeError: 'Node' object is not callable

C AttributeError: 'NoneType' object has no attribute 'val'

D NameError: name 'root' is not defined

💡 Hint

Check what root.left is before accessing val.

root.left is None, so trying to access val attribute on None raises AttributeError.

🚀 Application

advanced

How many nodes are in this binary tree?

Given the following binary tree node structure and code, how many nodes does the tree contain?

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

root = Node(8)
root.left = Node(3)
root.right = Node(10)
root.left.left = Node(1)
root.left.right = Node(6)
root.left.right.left = Node(4)
root.left.right.right = Node(7)
root.right.right = Node(14)
root.right.right.left = Node(13)

def count_nodes(node):
    if node is None:
        return 0
    return 1 + count_nodes(node.left) + count_nodes(node.right)

print(count_nodes(root))

A 9

B 8

C 10

D 7

💡 Hint

Count each node including root and all children recursively.

The tree has 9 nodes total: 8,3,10,1,6,4,7,14,13.

🧠 Conceptual

expert

What is the height of this binary tree?

Given the binary tree constructed below, what is its height? Height is the number of edges on the longest path from root to a leaf.

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

root = Node(20)
root.left = Node(10)
root.right = Node(30)
root.left.left = Node(5)
root.left.left.left = Node(2)
root.right.right = Node(40)
root.right.right.right = Node(50)
root.right.right.right.right = Node(60)

A 3

B 5

C 6

D 4

💡 Hint

Count edges from root to deepest leaf node.

The longest path is root(20) -> 30 -> 40 -> 50 -> 60 with 4 edges.

Practice

1. What does a typical binary tree node contain in its structure?

easy

A. A value and a reference to the parent node only

B. Only a value and a reference to the next node

C. A value, a reference to the left child, and a reference to the right child

D. A value and a list of all children nodes

Solution

1. Step 1: Understand binary tree node components

   A binary tree node typically stores a value and has two child references: left and right.

2. Step 2: Compare options with definition

   A value, a reference to the left child, and a reference to the right child matches this structure exactly, while others describe different data structures.

3. Final Answer:

   A value, a reference to the left child, and a reference to the right child -> Option C

4. Quick Check:

   Binary tree node = value + left + right [OK]

Hint: Binary tree nodes always have left and right child pointers [OK]

Common Mistakes:

• Confusing binary tree node with linked list node
• Thinking nodes have parent pointers by default
• Assuming children are stored in a list

2. Which of the following is the correct Python syntax to define a binary tree node class with attributes val, left, and right?

easy

A. class Node:
def __init__(self, val):
val = self
left = None
right = None

B. class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None

C. class Node:
def __init__(self):
self.val = None
self.left = None
self.right = None

D. class Node:
def __init__(self, val, left, right):
self.val = val
self.left = left
self.right = right

Solution

1. Step 1: Check constructor parameters and attribute assignments

   class Node: def __init__(self, val): self.val = val self.left = None self.right = None correctly initializes val and sets left and right to None by default.

2. Step 2: Validate syntax correctness

   class Node: def __init__(self, val): val = self left = None right = None incorrectly assigns variables; class Node: def __init__(self): self.val = None self.left = None self.right = None misses val parameter; class Node: def __init__(self, val, left, right): self.val = val self.left = left self.right = right requires left and right on init which is less common.

3. Final Answer:

   class Node: def __init__(self, val): self.val = val self.left = None self.right = None -> Option B

4. Quick Check:

   Constructor sets val and initializes children to None [OK]

Hint: Init val, set left and right to None inside __init__ [OK]

Common Mistakes:

• Not using self to assign attributes
• Forgetting to initialize left and right
• Incorrect parameter order or missing parameters

3. What will be the output of the following code snippet?

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

root = Node(10)
root.left = Node(5)
root.right = Node(15)
print(root.left.val, root.right.val)

medium

A. 15 5

B. 10 5

C. None None

D. 5 15

Solution

1. Step 1: Trace node creation and assignments

   Root node has value 10; left child is assigned a node with value 5; right child assigned node with value 15.

2. Step 2: Print left and right child values

   Printing root.left.val and root.right.val outputs 5 and 15 respectively.

3. Final Answer:

   5 15 -> Option D

4. Quick Check:

   Left child val = 5, Right child val = 15 [OK]

Hint: Print left.val and right.val after assignment to get child values [OK]

Common Mistakes:

• Printing root.val instead of children
• Confusing left and right child values
• Assuming children are None without assignment

4. Identify the error in the following binary tree node class definition:

class Node:
    def __init__(self, val):
        val = self.val
        left = None
        right = None

medium

A. Attributes are assigned incorrectly; should use self.val, self.left, self.right

B. Missing return statement in __init__ method

C. Class name should be lowercase

D. No error; code is correct

Solution

1. Step 1: Review attribute assignments in __init__

   Attributes must be assigned to self to belong to the instance, e.g., self.val = val.

2. Step 2: Identify incorrect assignments

   Code assigns val = self.val which reverses assignment and does not use self for left and right.

3. Final Answer:

   Attributes must be assigned using self, not local variables -> Option A

4. Quick Check:

   Use self.attr = value to set instance variables [OK]

Hint: Always assign attributes with self.attribute = value [OK]

Common Mistakes:

• Assigning variables without self prefix
• Reversing assignment order
• Expecting return in __init__

5. Given the following binary tree node class, how would you create a tree with root value 1, left child 2, and right child 3, then print the root and its children values?

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

hard

A. root = Node(1)
root.left = Node(2)
root.right = Node(3)
print(root.val, root.left.val, root.right.val)

B. root = Node(1, Node(2), Node(3))
print(root.val, root.left.val, root.right.val)

C. root = Node()
root.val = 1
root.left = 2
root.right = 3
print(root.val, root.left, root.right)

D. root = Node(1)
root.left = 2
root.right = 3
print(root.val, root.left, root.right)

Solution

1. Step 1: Create root node with value 1

   Use Node(1) to create root with val=1 and children None.

2. Step 2: Assign left and right children as Node instances

   Assign root.left = Node(2) and root.right = Node(3) to create child nodes properly.

3. Step 3: Print values of root and children

   Print root.val, root.left.val, root.right.val to get 1 2 3.

4. Final Answer:

   Use separate Node instances for children and print their val attributes -> Option A

5. Quick Check:

   Children must be Node objects, not integers [OK]

Hint: Assign children as Node objects, then print their val attributes [OK]

Common Mistakes:

• Assigning children as integers instead of Node objects
• Using constructor with extra parameters (not defined)
• Printing child nodes directly without .val