Tree vs Array vs Linked List When Hierarchy Matters in DSA Python - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Traversing a Simple Tree Structure

Consider this simple tree represented as nested lists. What will be the output of the preorder traversal?

DSA Python

def preorder(tree):
    if not tree:
        return []
    root, children = tree[0], tree[1:]
    result = [root]
    for child in children:
        result.extend(preorder(child))
    return result

tree = ['A', ['B', ['D'], ['E']], ['C', ['F']]]
print(preorder(tree))

A ['A', 'B', 'C', 'D', 'E', 'F']

B ['A', 'B', 'E', 'D', 'C', 'F']

C ['A', 'B', 'D', 'E', 'C', 'F']

D ['A', 'C', 'F', 'B', 'D', 'E']

💡 Hint

Preorder means visit root first, then children from left to right.

The preorder traversal visits the root node first, then recursively visits each child subtree from left to right. So the output is ['A', 'B', 'D', 'E', 'C', 'F'].

🧠 Conceptual

intermediate

Choosing Data Structure for Hierarchical Data

Which data structure is best to represent a company's organizational chart where each employee can have multiple subordinates?

A Tree, because it naturally represents hierarchical relationships

B Linked List, because it allows easy insertion and deletion

C Array, because it stores elements in order

D Stack, because it follows last-in-first-out order

💡 Hint

Think about parent-child relationships and multiple children per node.

A tree structure is best for hierarchical data like an organizational chart because it can represent parent-child relationships with multiple children per node naturally.

🔧 Debug

advanced

Why Does This Linked List Code Fail to Represent Hierarchy?

This code tries to represent a hierarchy using a singly linked list. What is the main problem?

DSA Python

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

# Trying to represent a manager with two subordinates
manager = Node('Manager')
sub1 = Node('Subordinate1')
sub2 = Node('Subordinate2')
manager.next = sub1
sub1.next = sub2

# Print chain
current = manager
while current:
    print(current.value)
    current = current.next

A The code has a syntax error in class definition

B Linked list cannot represent multiple children from one parent node

C The print loop will cause an infinite loop

D The nodes are not linked correctly because next pointers are missing

💡 Hint

Think about how many children a node can have in a singly linked list.

A singly linked list allows only one next node, so it cannot represent multiple children from one parent node, which is needed for hierarchy.

❓ Predict Output

advanced

Output of Flattening a Tree into an Array

What is the output of this code that flattens a tree into an array using depth-first search?

DSA Python

def flatten(tree):
    result = []
    def dfs(node):
        if not node:
            return
        result.append(node['value'])
        for child in node.get('children', []):
            dfs(child)
    dfs(tree)
    return result

tree = {
    'value': 1,
    'children': [
        {'value': 2, 'children': [{'value': 4}, {'value': 5}]},
        {'value': 3}
    ]
}
print(flatten(tree))

A [1, 2, 4, 5, 3]

B [1, 3, 2, 4, 5]

C [4, 5, 2, 3, 1]

D [1, 2, 3, 4, 5]

💡 Hint

Depth-first search visits node before children, left to right.

The DFS visits root 1, then child 2 and its children 4 and 5, then child 3, producing [1, 2, 4, 5, 3].

🧠 Conceptual

expert

Why Are Trees Preferred Over Arrays for Hierarchical Data?

Which reason best explains why trees are preferred over arrays when representing hierarchical data?

A Arrays can only store numbers, trees can store any data type

B Arrays use less memory than trees for hierarchical data

C Trees store data contiguously in memory unlike arrays

D Trees allow dynamic branching and represent parent-child links explicitly, arrays do not

💡 Hint

Think about how hierarchy and branching are represented.

Trees explicitly represent parent-child relationships and allow nodes to have multiple children, which arrays cannot do naturally.

Practice

1. Which data structure is best suited to represent hierarchical relationships like a family tree?

easy

A. Linked List

B. Array

C. Stack

D. Tree

Solution

1. Step 1: Understand hierarchy representation

   Hierarchies have parent-child relationships, which are naturally modeled by trees.

2. Step 2: Compare data structures

   Arrays and linked lists are linear and do not represent branching well, unlike trees.

3. Final Answer:

   Tree -> Option D

4. Quick Check:

   Hierarchy = Tree [OK]

Hint: Hierarchy means branching; trees model branching best [OK]

Common Mistakes:

• Choosing array for hierarchy
• Confusing linked list with tree
• Ignoring parent-child relationships

2. Which of the following is the correct way to declare a linked list node in Python?

easy

A. class Node:
def __init__(self, data):
self.data = data
self.prev = None

B. class Node:
def __init__(self, data):
self.data = data
self.next = None

C. class Node:
def __init__(self, data):
self.next = data
self.data = None

D. class Node:
def __init__(self):
self.data = None
self.next = None

Solution

1. Step 1: Identify linked list node structure

   A linked list node stores data and a pointer to the next node.

2. Step 2: Check each option

   class Node: def __init__(self, data): self.data = data self.next = None correctly assigns data and next pointer; others have incorrect attributes or missing data.

3. Final Answer:

   class Node: def __init__(self, data): self.data = data self.next = None -> Option B

4. Quick Check:

   Node has data and next pointer [OK]

Hint: Node must have data and next pointer for linked list [OK]

Common Mistakes:

• Swapping data and next attributes
• Missing next pointer
• Using prev pointer for singly linked list

3. You need to store a company's organizational chart with multiple levels of management and employees. Which data structure is best and why? A) Array because it stores data contiguously B) Linked List because it allows easy insertion C) Stack because it follows last-in-first-out order D) Tree because it naturally models multiple levels and branches

easy

A. Tree because it naturally models multiple levels and branches

B. Linked List because it allows easy insertion

C. Stack because it follows last-in-first-out order

D. Array because it stores data contiguously

Solution

1. Step 1: Understand organizational chart structure

   It has multiple levels with managers and subordinates, forming a hierarchy.

2. Step 2: Match data structure to hierarchy

   Tree structure models multiple levels and branches naturally, unlike arrays or linked lists which are linear.

3. Step 3: Eliminate other options

   Array is linear and fixed size; linked list is linear; stack is LIFO, not hierarchical.

4. Final Answer:

   Tree because it naturally models multiple levels and branches -> Option A

5. Quick Check:

   Hierarchy needs tree structure [OK]

Hint: Hierarchy with branches = use tree [OK]

Common Mistakes:

• Choosing array for hierarchical data
• Confusing linked list insertion with hierarchy
• Using stack for hierarchical representation

4. What will be the output of the following code that builds a simple tree and prints the root's first child's data?

class Node:
    def __init__(self, data):
        self.data = data
        self.children = []

root = Node('root')
child1 = Node('child1')
child2 = Node('child2')
root.children.append(child1)
root.children.append(child2)
print(root.children[0].data)

medium

A. child1

B. root

C. child2

D. Error

Solution

1. Step 1: Understand tree node structure

   Each node has data and a list of children nodes.

2. Step 2: Trace code execution

   Root has two children: child1 and child2. root.children[0] is child1, so printing its data outputs 'child1'.

3. Final Answer:

   child1 -> Option A

4. Quick Check:

   First child data = child1 [OK]

Hint: Index 0 child of root is first added child [OK]

Common Mistakes:

• Printing root data instead of child
• Confusing child1 and child2 order
• Assuming error due to children list

5. Find the error in this linked list insertion code:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def insert_at_head(head, data):
    new_node = Node(data)
    new_node.next = head
    head = new_node
    return head

head = None
head = insert_at_head(head, 10)
head = insert_at_head(head, 20)
print(head.data)

medium

A. head is not updated outside function

B. new_node.next should be None

C. No error; prints 20

D. Node class missing prev pointer

Solution

1. Step 1: Analyze insert_at_head function

   Function creates new node, points it to current head, updates head to new node, and returns it.

2. Step 2: Check usage and output

   Head is updated by assignment after each insertion. Printing head.data after two insertions prints 20, the last inserted value.

3. Final Answer:

   No error; prints 20 -> Option C

4. Quick Check:

   Head updated correctly, output 20 [OK]

Hint: Function returns new head; assign it back [OK]

Common Mistakes:

• Assuming head updates automatically without assignment
• Confusing next pointer assignment
• Expecting error due to missing prev pointer