Search⌘ K
AI Features
Home
Courses
Data Structures & Algorithms In Go

Solution Review: Print All the Paths

Understand how to implement a depth-first traversal to print every path from the root to leaf nodes in a tree. This lesson guides you through using a stack to track nodes, printing paths at leaves, and managing recursion with efficient time and space complexity.

We'll cover the following...

Solution

For this problem, we’ll use a stack and follow the depth-first approach. Whenever we traverse a node, we’ll add that node to the stack. When we reach a leaf, we’ll print the whole list (from the root node to that leaf node). When we return from the function, we’ll remove the element that was added to the stack when we entered this function.

Solution code

Go (1.6.2)
package main
import "fmt"
func (t *Tree) PrintAllPath() {
    stk := new(Stack)
    printAllPath(t.root, stk)
}
func printAllPath(curr *Node, stk *Stack) {
    
    if curr == nil {
        return
    }
    stk.Push(curr.value)
    if curr.left == nil && curr.right == nil {
        stk.Print()
        fmt.Println()
        stk.Pop()
        return
    }
    printAllPath(curr.right, stk)
    printAllPath(curr.left, stk)
    
    stk.Pop()
}
/* Testing Code */
func main() {
    arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    t := LevelOrderBinaryTree(arr)
    t.PrintAllPath()
}

Complexity analysis

The time and space complexity of this solution is O(n)O(n).

Explanation

  • Lines 15 to 21: We start by pushing the current node to the stack. If the node we just pushed is a leaf, we print the path from root to this leaf by using stk.Print(). Then we remove the current entry from the top of the stack to explore a sibling tree (if it exists) as shown in line 19.

  • Lines 23–24: If the current node is not a leaf then we continue our tree traversal.

  • Line 26: At the end of the function, we pop the node from the stack which is explored fully.