Tree Basics & Tricks

⚠️ This post was created when I was in high school and is no longer maintained.

1. Tree Properties

1. The depth of a node is the number of edges from the node to the tree’s root node. A root node will have a depth of 0.

2. The height of a node is the number of edges on the longest path from the node to a leaf. A leaf node will have a height of 0.

3. The height of a tree is the height of the root or the maximal depth. (For a complete binary tree, its height is Θ(lgn) )

4. A level or layer of a tree consists of all nodes of the same depth The number of levels is the height of the tree + 1.

2. Tree normal traversal

There are several ways to implement a Tree. The most common one is using a linked data structure in which, in addition to a key and satellite data each node has left, right and parents pointers.

<1> InOrder Traversal Visit left sub-tree, then node itself, then right sub-tree

algorithm InOrderTravesal(n):
    if n != NIL then
        InOrderTraversal(n.left)
-- only visit(print) itself when returning from the left sub-tree --
        Visit(n) 
        InOrderTraversal(n.right)

Output: 2, 5, 5, 6, 7, 8

<2> PostOrder Traversal Visit all successors and then the node itself

algorithm PostOrderTraversal(n):
    if m.left != NIL then
        PostOrderTraversal(n.left)
    if m.right != NIL then
        PostOrderTraversal(n.right)
    Visit(n)
-- only visit(print) itself when returning from both sub-tree --

Output:

(Numbers represent traversal order)

<3> PreOrder Traversal Visit the node first and then its successors

algorithm PreOrderTraversal(n):
    Visit(n)
    if m.left != NIL then
        PostOrderTraversal(n.left)
    if m.right != NIL then
        PostOrderTraversal(n.right)

Tip:

• I think of the recursive calls as placeholders for execution order: the code under an entry runs only when that call returns.
• The .left and .right pointers for a leaf are both NIL, so for inorder traversal we could use if n.left != NIL and n.right != NIL then ... to reason about the flow.
• To understand these traversals, remember the chosen order must hold for every subtree.

---

4. Tree traversal augmentations (tricks)

There are some interesting implementations of traversing a tree structure I’d like to share:

1. Non-recursive preorder traversal:

Algorithm NonRecurPreOrder(startNode):
    S := new Stack
    Push(S, startNode)
    
    While not S.isEmpty() do
        node := Pop(S)
        
        While node != NIL do:
            Visit(node)
            Push(S, node.right)
            node := node.left

1. Non-recursuve inorder traversal:

Algorithm NonRecurInOrder(startNode):
    if startNode == NIL then return
    
    S := new Stack
    Push(S, startNode)
    node := startNode
    
    While not S.isEmpty() do
        While node.left != NIL do
            node := node.left
            Push(S, node)
        
        node := Pop(S)
        Visit(node)
        -- the most beatiful logic is here --
        if node.right != NIL then 
            node := node.right
            Push(S, node)

---

5. InOrder Traversal Time Complexcity

\(T(n) = Θ(n)\) Proof:

---

6. Today’s special

Reverse a singly linked list non-recursively in Θ(n)

Algorithm ReserveSLL(L):
    if L.head == NIL then
        return
    
    prevPtr := L.head 
    prevPtr.next := NIL     --> after reversing, L.head becomes the new tail, so next should be NIL
    currPtr := L.head.next  --> starts from the second node (head.next)
    nextPtr := NIL
    
    While currPtr != NIL do
        nextPtr := currPtr.next
        currPtr.next := prePtr
        prevPtr := currPtr
        currPtr := nextPtr
    
    L.head := prevPtr --> Don't forget to set the head at the end