Trees and hierarchical data in Intro to Computing - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ trace

intermediate

Trace the output of a simple tree traversal

Consider a tree where each node has a value and up to two children (left and right). The traversal visits nodes in this order: root, left child, right child.

What is the output sequence of node values for the tree below?

    10
   /  \
  5    15
 /    /  \
3    12  20

Intro to Computing

def preorder(node):
    if node is None:
        return []
    return [node.value] + preorder(node.left) + preorder(node.right)

# Tree structure:
# Node(10, left=Node(5, left=Node(3)), right=Node(15, left=Node(12), right=Node(20)))

# Call preorder(root)

A [5, 3, 10, 15, 12, 20]

B [3, 5, 10, 12, 15, 20]

C [10, 15, 20, 12, 5, 3]

D [10, 5, 3, 15, 12, 20]

💡 Hint

Preorder traversal visits the root node first, then recursively visits the left subtree, then the right subtree.

The preorder traversal visits nodes in the order: root, left subtree, right subtree. Starting at 10, then 5, then 3, then back up to 15, then 12, then 20.

🧠 Conceptual

intermediate

Identify the correct tree property

Which of the following statements correctly describes a binary search tree (BST)?

A For every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater.

B Every node has exactly two children, and the tree is perfectly balanced.

C Nodes are arranged so that the sum of values in the left subtree equals the sum in the right subtree.

D The tree is stored as a linked list with nodes connected only to their next sibling.

💡 Hint

Think about the ordering rule that defines a binary search tree.

A binary search tree requires that for each node, all values in the left subtree are less than the node's value, and all values in its right subtree are greater. This property allows efficient searching.

❓ Comparison

advanced

Compare tree traversal outputs

Given the same binary tree, which traversal method produces the nodes in ascending order if the tree is a binary search tree?

A Preorder traversal (root, left, right)

B Postorder traversal (left, right, root)

C Inorder traversal (left, root, right)

D Level-order traversal (breadth-first)

💡 Hint

Consider which traversal visits nodes in sorted order for a BST.

Inorder traversal visits the left subtree, then the root, then the right subtree. For a BST, this results in nodes being visited in ascending order.

❓ identification

advanced

Identify the error in tree node insertion

Consider the following pseudocode for inserting a value into a binary search tree:

function insert(node, value):
  if node is None:
    return new Node(value)
  if value < node.value:
    insert(node.left, value)
  else:
    insert(node.right, value)
  return node

What is the main problem with this code?

A It does not update the left or right child pointers after recursive insertion.

B It returns None instead of the updated node.

C It creates a new node even when the current node is not None.

D It incorrectly compares values using less than instead of greater than.

💡 Hint

Think about how recursive calls affect the tree structure and what must be done to keep the tree updated.

The recursive calls insert the new node but do not assign the returned node to the parent's left or right pointer, so the tree structure does not update correctly.

🚀 Application

expert

Calculate the height of a tree

Given the following tree structure, what is the height of the tree?

        A
       / \
      B   C
     /   / \
    D   E   F
       /     \
      G       H
               \
                I

Height is defined as the number of edges on the longest path from the root to a leaf.

A 5

B 4

C 3

D 6

💡 Hint

Trace the longest path from root A to the deepest leaf node.

The longest path is A -> C -> F -> H -> I, which has 4 edges, so the height is 4.