Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA Python - Performance Analysis

Time Complexity: Why Trees Exist and What Linked Lists and Arrays Cannot Do

O(n) for array and linked list, O(log n) for balanced binary search tree

Understanding Time Complexity

We want to understand why trees are used instead of just arrays or linked lists.

What makes trees faster or better for some tasks?

Scenario Under Consideration

Analyze the time complexity of searching for a value in different data structures.

# Search in an unsorted array
def search_array(arr, target):
    for item in arr:
        if item == target:
            return True
    return False

# Search in a linked list
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

def search_linked_list(head, target):
    current = head
    while current:
        if current.val == target:
            return True
        current = current.next
    return False

# Search in a binary search tree
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def search_bst(root, target):
    if not root:
        return False
    if root.val == target:
        return True
    elif target < root.val:
        return search_bst(root.left, target)
    else:
        return search_bst(root.right, target)
    

This code shows searching for a value in an array, a linked list, and a binary search tree.

Identify Repeating Operations

Look at what repeats when searching:

• Primary operation: Checking each element or node for the target value.
• How many times: In array and linked list, up to n times (all elements). In tree, depends on height (usually less than n).

How Execution Grows With Input

As the number of items grows, how many checks do we do?

Input Size (n)	Array/Linked List Checks	Binary Search Tree Checks
10	Up to 10	About 4 (height ~ log2(10))
100	Up to 100	About 7 (height ~ log2(100))
1000	Up to 1000	About 10 (height ~ log2(1000))

Pattern observation: Array and linked list checks grow directly with n, but tree checks grow much slower, roughly with the height of the tree.

Final Time Complexity

Time Complexity: O(n) for array and linked list search, O(log n) for balanced binary search tree search

This means searching in trees can be much faster than arrays or linked lists as data grows.

Common Mistake

[X] Wrong: "Trees are always faster than arrays or linked lists for any operation."

[OK] Correct: Trees are faster for search if balanced, but arrays are faster for simple access by index, and linked lists can be better for easy insertions at ends.

Interview Connect

Understanding why trees exist helps you choose the right data structure for the job, a key skill in coding interviews and real projects.

Self-Check

"What if the binary search tree is not balanced? How would the time complexity change?"

Practice

1. Why do trees exist as a data structure when we already have arrays and linked lists?

easy

A. Because trees can represent hierarchical relationships which arrays and linked lists cannot

B. Because trees use less memory than arrays and linked lists

C. Because trees are easier to implement than arrays and linked lists

D. Because trees always provide faster access than arrays and linked lists

Solution

1. Step 1: Understand the limitation of arrays and linked lists

   Arrays and linked lists store data in a linear order, which makes it hard to represent hierarchical or branching relationships.

2. Step 2: Identify the unique feature of trees

   Trees allow nodes to have multiple children, representing parent-child relationships naturally, which arrays and linked lists cannot do efficiently.

3. Final Answer:

   Trees represent hierarchical relationships which arrays and linked lists cannot -> Option A

4. Quick Check:

   Hierarchy needs trees = A [OK]

Hint: Trees model hierarchy; arrays and lists are linear [OK]

Common Mistakes:

• Thinking trees always use less memory
• Believing trees are simpler to implement
• Assuming trees always have faster access

2. Which of the following is the correct way to define a simple tree node class in Python?

easy

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

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

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

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

Solution

1. Step 1: Identify the tree node structure

   A tree node typically stores a value and a list of children nodes to represent branches.

2. Step 2: Match the class definition

   class Node: def __init__(self, value): self.value = value self.children = [] defines a node with a value and a children list, which fits a general tree node structure.

3. Final Answer:

   Node with value and children list -> Option C

4. Quick Check:

   Tree nodes have children list = D [OK]

Hint: Tree nodes have children list, not next or prev pointers [OK]

Common Mistakes:

• Using 'next' pointer like in linked lists
• Using 'prev' pointer which is for doubly linked lists
• Adding unrelated pointers like 'next' in trees

3. What will be the output of this code that tries to print values in a simple tree node?

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

root = Node(1)
child1 = Node(2)
child2 = Node(3)
root.children.append(child1)
root.children.append(child2)

for child in root.children:
    print(child.value)

medium

A. Error: 'Node' object is not iterable

B. 1 2 3

C. 1

D. 2 3

Solution

1. Step 1: Understand the tree structure created

   Root node has value 1 and two children nodes with values 2 and 3.

2. Step 2: Trace the loop printing child values

   The loop iterates over root.children, printing each child's value: 2 then 3.

3. Final Answer:

   2 3 -> Option D

4. Quick Check:

   Children values printed = A [OK]

Hint: Loop prints children values, not root value [OK]

Common Mistakes:

• Printing root value inside loop
• Confusing children list with node itself
• Expecting root value to print in loop

4. Find the error in this code that tries to add a child to a tree node:

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

root = Node(1)
child = Node(2)
root.children.append(child)

medium

A. append() method does not exist for lists

B. children should be initialized as an empty list, not None

C. Node class should not have a children attribute

D. Cannot create child nodes before root node

Solution

1. Step 1: Check children initialization

   children is set to None, so it is not a list and cannot use append().

2. Step 2: Identify correct initialization

   children should be an empty list [] to allow appending child nodes.

3. Final Answer:

   children should be initialized as an empty list, not None -> Option B

4. Quick Check:

   children must be list for append() [OK]

Hint: Initialize children as [] to use append() [OK]

Common Mistakes:

• Setting children to None instead of list
• Trying to append to None type
• Ignoring initialization of children attribute

5. You want to represent a company's organizational chart where each employee can have multiple subordinates. Which data structure is best and why?

hard

A. Tree, because it naturally models hierarchical relationships

B. Array, because it stores data in order

C. Linked list, because it connects employees one after another

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

Solution

1. Step 1: Understand the problem context

   An organizational chart shows who reports to whom, forming a hierarchy with multiple subordinates per employee.

2. Step 2: Match data structure to hierarchy

   Trees allow each node (employee) to have multiple children (subordinates), perfectly modeling this hierarchy.

3. Final Answer:

   Tree, because it naturally models hierarchical relationships -> Option A

4. Quick Check:

   Hierarchy needs trees = B [OK]

Hint: Hierarchy means use trees, not linear structures [OK]

Common Mistakes:

• Choosing arrays or lists for hierarchical data
• Confusing stack usage with hierarchy
• Ignoring multiple children per node