Paths in Binary Search Tree

Tags: , , , ,

Print paths in binary search tree

Print paths in binary search tree from root to leaf node. There can be many paths in a tree. AT every node, there are two paths splitting. Maximum length of path in binary search tree can be N nodes. Consider following tree:

paths in binary search tree

Paths in given binary search tree are : [ 10,5,1 ], [10,5,6 ], [10,19,17 ], [10,19,20]

Paths in binary search tree : Algorithm

As every path start with root node, it’s obvious that first node in every path with root node.  At root node, we have two choices. We can go to left subtree or can go to right subtree. It does not matter what subtree we go first as we have to traverse all paths anyway.

Let’s say we traverse left subtree first. At this point, we have first node in path, all we need to find all paths in left subtree and append those path with first node we have.
At first left child, problem remains the same, find paths in binary search tree. Additional step is to append to existing path we have already have covered. Are you getting a hint on recursive nature of problem?

Once, we have traversed all paths on left subtree, it’s time to traverse all paths on right subtree.

To keep track of nodes which are already added to path, we have to maintain a list of nodes, which will be updated whenever we move up and down in BST.

As mentioned, path ends on leaf node, as soon as we hit a node which has no left or right child, start going back up in the tree. In implementation terms, this will be termination condition for recursive function. Algorithm to print paths in binary tree.

Paths in binary search tree : Implementation

#include<stdio.h>
#include<stdlib.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};

typedef struct node Node;

void printPaths(Node * node, int path[], int pathLen){
	
  	int i;
	
	if(!node)
		return;
	
	path[pathLen]  = node->value;
	
	int isLeaf = ! ( node->left || node->right ) ;
	if(isLeaf ){
		printf("\n Path till node %d is :", node->value);
		for(i=0; i<=pathLen; i++){
			printf("%d, ", path[i]);
		}
	}

	printPaths(node->left,  path, pathLen+1);
	printPaths(node->right, path, pathLen+1);
	
	return ;
}

Node * createNode(int value){
  Node *newNode =  (Node *)malloc(sizeof(Node));
  
  newNode->value = value;
  newNode->right= NULL;
  newNode->left = NULL;
  
  return newNode;
  
}

Node * addNode(Node *node, int value){
  if(node == NULL){
      return createNode(value);
  }
  else{
     if (node->value > value){
        node->left = addNode(node->left, value);
      }
      else{
        node->right = addNode(node->right, value);
      }
  }
  return node;
}
 
/* Driver program for the function written above */
int main(){
  Node *root = NULL;
  int n = 0;
  //Creating a binary tree
  root = addNode(root,30);
  root = addNode(root,20);
  root = addNode(root,15);
  root = addNode(root,25);
  root = addNode(root,40);
  root = addNode(root,37);
  root = addNode(root,45);
  int path[100];
  printPaths(root, path, 0);
  
  return 0;
}

Java implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    private Node root;

    public void BinarySearchTree(){
        root = null;
    }

    public class Node {
        private int value;
        private  Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }

    private Node insertNode(Node root, int value){
        if(root == null){
            //if this node is root of tree
            root = new Node(value);
        }
        else{
            if(root.value > value){
                //If root is greater than value, node should be added to left subtree
                root.left = insertNode(root.left, value);
            }
            else{
                //If root is less than value, node should be added to right subtree
                root.right = insertNode(root.right, value);
            }
        }
        return root;
    }

    public void printPath(){
        ArrayList<Node> path  = new ArrayList<>();
        this.printPathRecursive(this.root, path);
    }

    private void printPathRecursive(Node root, ArrayList<Node> path){
        if(root == null) return;
        path.add(root);

        //If node is leaf node
        if(root.left == null && root.right == null){
            path.forEach(node -> System.out.print(" " + node.value));
            path.remove(path.size()-1);
            System.out.println();
            return;
        }

        printPathRecursive(root.left,path);
        printPathRecursive(root.right, path);

        path.remove(path.size()-1);

    }
}

Test class

package com.company.BST;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTreeTests {
    public static void main (String[] args){
        BinarySearchTree binarySearchTree = new BinarySearchTree();

        binarySearchTree.insert(7);
        binarySearchTree.insert(8);
        binarySearchTree.insert(6);
        binarySearchTree.insert(9);
        binarySearchTree.insert(3);
        binarySearchTree.insert(4);

        binarySearchTree.printPath();
    }
}

Since we are traversing each node at least once, complexity of  implementation for print all paths in binary search tree is  O(n) where n is number of nodes.

Please share if there is something wrong or missing. If you want to contribute and share your knowledge with thousands of learners across world, please reach out to us at communications@algorithmsandme.com.