All root-to-leaf paths of a Binary tree

Write a program to find all root to leaf paths of a Binary tree. A tree has different paths from the root to each leaf node, print all the possible paths from the root to each leaf node separately.

A tree has different paths from the root to each leaf node. We have to print all the possible paths from the root to each leaf node separately.

All root-to-leaf paths of a Binary tree example

For this graph all possible root to leaf paths are

1 -> 2 -> 4
1 -> 2 -> 5
1 -> 3 -> 6 -> 8
1 -> 3 -> 7 -> 9

Example -

Input: 
      1
    /   \
   2     3
  / \   / \
 4   5 6   7

Output: 
    1 -> 2 -> 4
    1 -> 2 -> 5
    1 -> 3 -> 6
    1 -> 3 -> 7

Solution

For the solution, we have to traverse each node recursively and find all the possible paths for each leaf node from the root.

Python

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

def path_finder_util(root, string, paths):
    if not root: return
    string += str(root.data)
    path_finder_util(root.left, string+'->', paths)
    path_finder_util(root.right, string+'->', paths)
    if not root.left and not root.right:
        paths.append(string)

def path_finder(root):
    if not root:
        print("")
        return
    paths = []
    path_finder_util(root, '', paths)
    for path in paths:
        print(path)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.right.left.left = Node(8)
root.right.right.right = Node(9)
path_finder(root)

JavaScript

class Node {
  constructor(data) {
    this.left = null;
    this.data = data;
    this.right = null;
  }
}

function pathFinderUtil(root, string, paths) {
  if (root == null) return;
  string = string + root.data;
  pathFinderUtil(root.left, string + "->", paths);
  pathFinderUtil(root.right, string + "->", paths);
  if (root.left == null && root.right == null) {
    paths.push(string);
  }
}

function pathFinder(root) {
  if (root == null) {
    console.log("");
    return;
  }
  let paths = [];
  pathFinderUtil(root, "", paths);
  for (let path of paths) {
    console.log(path);
  }
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.right.left.left = new Node(8);
root.right.right.right = new Node(9);
pathFinder(root);

Output

1->2->4
1->2->5
1->3->6->8
1->3->7->9

In the above program, we have printed all the root-to-leaf paths as a string but we may need all paths as a list to process further in that case we can use the following program.

Python

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

def path_finder_util(root, path, paths):
    path.append(root.data)
    if root.left:
        path_finder_util(root.left, path, paths)
    if root.right:
        path_finder_util(root.right, path, paths)
    if not root.left and not root.right:
        # store the copy of list to avoid referencing older list
        paths.append(path.copy())
    path.pop() # remove last node to backtrack

def path_finder(root):
    if not root:
        print([])
        return
    paths = []
    path_finder_util(root, [], paths)
    for path in paths:
        print(path)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.right.left.left = Node(8)
root.right.right.right = Node(9)
root = None
path_finder(root)

JavaScript

class Node {
  constructor(data) {
    this.left = null;
    this.data = data;
    this.right = null;
  }
}

function pathFinderUtil(root, path, paths) {
  path.push(root.data);
  if (root.left) {
    pathFinderUtil(root.left, path, paths);
  }
  if (root.right) {
    pathFinderUtil(root.right, path, paths);
  }
  if (root.left == null && root.right == null) {
    // store the copy of list to avoid referencing older list
    paths.push([...path]);
  }
  path.pop(); // remove last node to backtrack
}

function pathFinder(root) {
  if (root == null) {
    console.log([]);
    return;
  }
  let paths = [];
  pathFinderUtil(root, [], paths);
  for (let path of paths) {
    console.log(path);
  }
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.right.left.left = new Node(8);
root.right.right.right = new Node(9);
pathFinder(root);

Output

[1, 2, 4]
[1, 2, 5]
[1, 3, 6, 8]
[1, 3, 7, 9]

All root-to-leaf paths of a Binary tree

All root-to-leaf paths of a Binary tree

Solution

Recommended Posts