Linked Lists and Trees in Python from Scratch: Node Classes, Traversals, and Interview Problems

Python hides pointers behind object references. That is convenient until an interviewer asks you to build a linked list, reverse it in place, or explain why a tree traversal works. The cure is to treat every reference as a visible arrow and follow what happens to that arrow one assignment at a time.

Node classes in Python: ListNode and TreeNode

A linked list is not a special Python container. It is a chain of ordinary objects, where each object stores a value and a reference to the next object.

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

Here, self.next is the pointer. It starts as None, which means there is no next node yet. A binary tree node uses the same idea but keeps two outgoing references:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Set these attributes inside __init__ so every node carries its own instance state. A class-level next = None is only a shared fallback until an instance shadows it. That can conceal incomplete initialisation and make the structure much harder to reason about.

Building and walking a linked list

To build 10 -> 20 -> 30 -> 40, create four nodes and connect their references:

head = ListNode(10)
head.next = ListNode(20)
head.next.next = ListNode(30)
head.next.next.next = ListNode(40)

head is the one reference that gives access to the whole chain. A traversal uses a separate cursor so that head remains safe:

cur = head
while cur is not None:
    print(cur.data)
    cur = cur.next

After the node containing 40, cur.next is None, so the loop ends. If you move head itself during traversal and do not save it, you lose the entry point to the list.

Inserting at the head is constant time. Set the new node's next to the old head, then move head to the new node. Inserting at the tail takes O(n) if you must walk from the head, but O(1) if the structure also maintains a valid tail reference.

Reversing a linked list in place

Reversal needs three references: prev, cur, and nxt. The temporary reference matters because changing cur.next cuts the only forward link to the unprocessed part.

def reverse(head):
    prev = None
    cur = head

    while cur is not None:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt

    return prev

Trace it on 10 -> 20 -> 30 -> 40 -> None, starting with prev = None and cur = 10. Each numbered step below is one pass of the loop:

1. Save 20, point 10 to None, then move prev to 10 and cur to 20. The reversed part is 10 -> None.

2. Save 30, point 20 to 10, then move prev to 20 and cur to 30. The reversed part is 20 -> 10 -> None.

3. Save 40, point 30 to 20, then move prev to 30 and cur to 40. The reversed part is 30 -> 20 -> 10 -> None.

4. Save None, point 40 to 30, then move prev to 40 and cur to None. The loop stops.

Step 2 leaves two links reversed. Step 3 then reads nxt = cur.next without redirecting it, so at that instant prev is 20, cur is 30, and nxt is 40, exactly as the figure shows.

When the loop ends, cur has moved past the old tail and prev points to the new head. Returning prev therefore gives 40 -> 30 -> 20 -> 10 -> None. The crucial order is save, redirect, advance. Redirect before saving and the unreversed suffix is lost.

Building a binary search tree from scratch

A binary search tree, or BST, keeps smaller values in the left subtree and larger values in the right subtree. This recursive insertion function expresses that rule directly:

def insert(root, value):
    if root is None:
        return TreeNode(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

Insert 8, 3, 10, 1, 6, 14 into an empty tree. The steps are:

• 8 becomes the root.

• 3 is smaller than 8, so it becomes the left child of 8.

• 10 is larger than 8, so it becomes the right child of 8.

• 1 goes left at 8 and left again at 3.

• 6 goes left at 8, then right at 3.

• 14 goes right at 8, then right at 10.

The final root is 8. Its left child is 3, with children 1 and 6. Its right child is 10, whose right child is 14.

An inorder traversal visits left subtree, node, then right subtree. It produces 1, 3, 6, 8, 10, 14, which is sorted. Preorder visits node first and produces 8, 3, 1, 6, 10, 14. That sorted inorder result is a powerful BST invariant and the basis of many validation questions. The binary trees and binary search trees guide develops the wider set of traversal and operation patterns.

Interview problems that reuse these patterns

The standard list and tree interview problems are variations on the same node-movement templates. Finding the middle of the list is the clearest example. On 10 -> 20 -> 30 -> 40 -> None, both slow and fast start at the head, 10, and the loop runs while fast and fast.next both exist.

1. In the first step, fast can see 10 and then 20, so slow moves to 20 while fast jumps to 30.

2. In the second step, fast sees 30 and then 40, so slow moves to 30 while fast jumps past 40 to None.

The loop now ends, leaving slow on 30, the second of the two middle nodes, 20 and 30. To return the first middle, 20, loop only while fast.next and fast.next.next both exist, so the pointers stop one step sooner, which makes the even-length choice explicit.

Cycle detection reuses the same one-step and two-step speeds: a meeting between slow and fast confirms a cycle, while fast or fast.next reaching None confirms there is no cycle. To merge two sorted lists, keep a dummy head and splice in the smaller current node each time, so the first output node needs no special case. Tree height is one plus the larger of the left and right subtree heights. For level-order traversal, push the root into a queue, pop one node, and enqueue its children, which produces breadth-first search.

Traps that cost the answer

The most common reversal bug is overwriting cur.next before storing the old next reference. Another is returning cur, which is None at loop exit, instead of returning prev.

Deep recursion is also a practical Python concern. A very long list or a badly skewed tree can exceed the interpreter's recursion limit and raise RecursionError. Prefer an iterative traversal when input depth is unknown. Finally, define a duplicate-value policy for a BST before coding. The insertion above sends duplicates right, but another problem may reject them.

The short version and your next step

In Python, an object reference plays the role of a pointer. Preserve the entry reference, save the next node before rewiring, and use the BST ordering rule to predict traversals.

Now type both implementations without copying them. The DSA Using Python course gives you the larger sequence in which to practise list operations, tree traversals, and the interview problems built on them.

Next, practise the same operations at length. The Data Structures module in Zero to Hero runs from arrays and stacks through linked lists and trees, with over 1,500 practice questions attached.