Posted on by Kalkicode
Code Recursion

Print all sorted path from root to leaf in binary tree

The problem at hand involves a binary tree and aims to find and print all sorted paths from the root to the leaf nodes. In other words, we want to identify paths in the tree where the values along the path are in ascending order.

Problem Statement

Given a binary tree, we need to find all the paths from the root to the leaf nodes where the values along the path are in ascending order. After identifying these paths, we need to print them.

Example

Consider the binary tree described in the code:


      4
    /   \
   4     7
  / \     \
 2   5     12
    / \    / \
   10  8  5   18
  /        \
 19         15

For this tree, the sorted paths from root to leaf nodes are:

  1. Path: 4 -> 4 -> 5 -> 10 -> 19
  2. Path: 4 -> 4 -> 5 -> 8
  3. Path: 4 -> 7 -> 12 -> 18

Idea to Solve

The problem can be solved using a recursive approach. Starting from the root of the binary tree, we traverse the tree while keeping track of the current path. At each node, we add the node's value to the path. If we reach a leaf node, we check if the path is in ascending order. If it is, we print the path. After processing a node, we move to its left and right children recursively.

Pseudocode


    function printPath(path):
    for element in path:
        print element
    print newline

function sortPath(node, path):
    if node is null:
        return
    add node.data to path
    if node is leaf node:
        if path is in ascending order:
            printPath(path)
    else:
        if node.left exists and node.left.data >= node.data:
            sortPath(node.left, path)
        if node.right exists and node.right.data >= node.data:
            sortPath(node.right, path)
    remove last element from path

function allSortedPath():
    create empty path list
    if root is null:
        return
    else:
        call sortPath(root, path)

main:
    create binary tree
    construct tree as shown
    call allSortedPath()

Algorithm Explanation

  1. The printPath function simply prints the elements of the given path.
  2. The sortPath function recursively traverses the binary tree, adding elements to the current path. When a leaf node is reached, if the path is sorted, it's printed.
  3. The allSortedPath function initializes an empty path list and calls the sortPath function with the root node.
  4. In the main function, a binary tree is constructed, and allSortedPath is called.

Program Solution

import java.util.ArrayList;
/*
    Java Program
    Print all sorted path from root to leaf in binary tree
*/
// Binary Tree node
class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		// Set initial tree root to null
		this.root = null;
	}
	// Display given path 
	public void printPath(ArrayList < Integer > path)
	{
		int i = 0;
		// print path
		while (i < path.size())
		{
			System.out.print(" " + path.get(i));
			i++;
		}
		System.out.print("\n");
	}
	//  Find and print sorted path using recursion
	public void sortPath(TreeNode node, ArrayList < Integer > path)
	{
		if (node == null)
		{
			return;
		}
		// Add path element
		path.add(node.data);
		if (node.left == null && node.right == null)
		{
			// Display calculated path
			printPath(path);
		}
		else
		{
			if (node.left != null && node.left.data >= node.data)
			{
				// When left node exists and its is ascending order
				sortPath(node.left, path);
			}
			if (node.right != null && node.right.data >= node.data)
			{
				// When right node exists and its is ascending order
				sortPath(node.right, path);
			}
		}
		// Remove last node in path
		path.remove(path.size() - 1);
	}
	// Handles the request of find all all sorted path root to leaf nodes
	public void allSortedPath()
	{
		// This is use to collect sort path
		ArrayList < Integer > path = new ArrayList < Integer > ();
		if (this.root == null)
		{
			// Empty Tree
			return;
		}
		else
		{
			sortPath(this.root, path);
		}
	}
	public static void main(String[] args)
	{
		// Create new binary tree
		BinaryTree tree = new BinaryTree();
		/*
		         4                            
		       /   \    
		      4     7    
		     / \     \               
		    2   5     12
		       / \    / \
		      10  8  5   18
		     /        \
		    19         15 
		-----------------
		Constructing binary tree
		                
		        
		*/
		tree.root = new TreeNode(4);
		tree.root.left = new TreeNode(4);
		tree.root.left.right = new TreeNode(5);
		tree.root.left.right.left = new TreeNode(10);
		tree.root.left.right.left.left = new TreeNode(19);
		tree.root.left.right.right = new TreeNode(8);
		tree.root.left.left = new TreeNode(2);
		tree.root.right = new TreeNode(7);
		tree.root.right.right = new TreeNode(12);
		tree.root.right.right.right = new TreeNode(18);
		tree.root.right.right.left = new TreeNode(5);
		tree.root.right.right.left.right = new TreeNode(15);
		tree.allSortedPath();
	}
}

input

 4 4 5 10 19
 4 4 5 8
 4 7 12 18
// Include header file
#include <iostream>
#include <vector>
using namespace std;

/*
    C++ Program
    Print all sorted path from root to leaf in binary tree
*/
// Binary Tree node
class TreeNode
{
	public: 
    int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		// Set node value
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class BinaryTree
{
	public: 
    TreeNode *root;
	BinaryTree()
	{
		this->root = NULL;
	}
	// Display given path
	void printPath(vector < int > path)
	{
		int i = 0;
		// print path
		while (i < path.size())
		{
			cout << " " << path.at(i);
			i++;
		}
		cout << "\n";
	}
	//  Find and print sorted path using recursion
	void sortPath(TreeNode *node, vector < int > path)
	{
		if (node == NULL)
		{
			return;
		}
		// Add path element
		path.push_back(node->data);
		if (node->left == NULL && node->right == NULL)
		{
			// Display calculated path
			this->printPath(path);
		}
		else
		{
			if (node->left != NULL && node->left->data >= node->data)
			{
				// When left node exists and its is ascending order
				this->sortPath(node->left, path);
			}
			if (node->right != NULL && node->right->data >= node->data)
			{
				// When right node exists and its is ascending order
				this->sortPath(node->right, path);
			}
		}
		// Remove last node in path
		path.pop_back();
	}
	// Handles the request of find all all sorted path root to leaf nodes
	void allSortedPath()
	{
		// This is use to collect sort path
		vector < int > path;
		if (this->root == NULL)
		{
			// Empty Tree
			return;
		}
		else
		{
			this->sortPath(this->root, path);
		}
	}
};
int main()
{
	// Create new binary tree
	BinaryTree *tree = new BinaryTree();
	/*
	         4                            
	       /   \    
	      4     7    
	     / \     \               
	    2   5     12
	       / \    / \
	      10  8  5   18
	     /        \
	    19         15 
	-----------------
	Constructing binary tree     
	*/
	tree->root = new TreeNode(4);
	tree->root->left = new TreeNode(4);
	tree->root->left->right = new TreeNode(5);
	tree->root->left->right->left = new TreeNode(10);
	tree->root->left->right->left->left = new TreeNode(19);
	tree->root->left->right->right = new TreeNode(8);
	tree->root->left->left = new TreeNode(2);
	tree->root->right = new TreeNode(7);
	tree->root->right->right = new TreeNode(12);
	tree->root->right->right->right = new TreeNode(18);
	tree->root->right->right->left = new TreeNode(5);
	tree->root->right->right->left->right = new TreeNode(15);
	tree->allSortedPath();
	return 0;
}

input

 4 4 5 10 19
 4 4 5 8
 4 7 12 18
// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp Program
    Print all sorted path from root to leaf in binary tree
*/
// Binary Tree node
public class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		// Set initial tree root to null
		this.root = null;
	}
	// Display given path
	public void printPath(List < int > path)
	{
		int i = 0;
		// print path
		while (i < path.Count)
		{
			Console.Write(" " + path[i]);
			i++;
		}
		Console.Write("\n");
	}
	//  Find and print sorted path using recursion
	public void sortPath(TreeNode node, List < int > path)
	{
		if (node == null)
		{
			return;
		}
		// Add path element
		path.Add(node.data);
		if (node.left == null && node.right == null)
		{
			// Display calculated path
			this.printPath(path);
		}
		else
		{
			if (node.left != null && node.left.data >= node.data)
			{
				// When left node exists and its is ascending order
				this.sortPath(node.left, path);
			}
			if (node.right != null && node.right.data >= node.data)
			{
				// When right node exists and its is ascending order
				this.sortPath(node.right, path);
			}
		}
		// Remove last node in path
		path.RemoveAt(path.Count - 1);
	}
	// Handles the request of find all all sorted path root to leaf nodes
	public void allSortedPath()
	{
		// This is use to collect sort path
		List < int > path = new List < int > ();
		if (this.root == null)
		{
			// Empty Tree
			return;
		}
		else
		{
			this.sortPath(this.root, path);
		}
	}
	public static void Main(String[] args)
	{
		// Create new binary tree
		BinaryTree tree = new BinaryTree();
		/*
		         4                            
		       /   \    
		      4     7    
		     / \     \               
		    2   5     12
		       / \    / \
		      10  8  5   18
		     /        \
		    19         15 
		-----------------
		Constructing binary tree     
		*/
		tree.root = new TreeNode(4);
		tree.root.left = new TreeNode(4);
		tree.root.left.right = new TreeNode(5);
		tree.root.left.right.left = new TreeNode(10);
		tree.root.left.right.left.left = new TreeNode(19);
		tree.root.left.right.right = new TreeNode(8);
		tree.root.left.left = new TreeNode(2);
		tree.root.right = new TreeNode(7);
		tree.root.right.right = new TreeNode(12);
		tree.root.right.right.right = new TreeNode(18);
		tree.root.right.right.left = new TreeNode(5);
		tree.root.right.right.left.right = new TreeNode(15);
		tree.allSortedPath();
	}
}

input

 4 4 5 10 19
 4 4 5 8
 4 7 12 18
<?php
/*
    Php Program
    Print all sorted path from root to leaf in binary tree
*/
// Binary Tree node
class TreeNode
{
	public $data;
	public $left;
	public $right;
	public	function __construct($data)
	{
		// Set node value
		$this->data = $data;
		$this->left = NULL;
		$this->right = NULL;
	}
}
class BinaryTree
{
	public $root;
	public	function __construct()
	{
		$this->root = NULL;
	}
	// Display given path
	public	function printPath($path)
	{
		$i = 0;
		// print path
		while ($i < count($path))
		{
			echo(" ".$path[$i]);
			$i++;
		}
		echo("\n");
	}
	//  Find and print sorted path using recursion
	public	function sortPath($node, $path)
	{
		if ($node == NULL)
		{
			return;
		}
		// Add path element
		$path[] = $node->data;
		if ($node->left == NULL && $node->right == NULL)
		{
			// Display calculated path
			$this->printPath($path);
		}
		else
		{
			if ($node->left != NULL && $node->left->data >= $node->data)
			{
				// When left node exists and its is ascending order
				$this->sortPath($node->left, $path);
			}
			if ($node->right != NULL && $node->right->data >= $node->data)
			{
				// When right node exists and its is ascending order
				$this->sortPath($node->right, $path);
			}
		}
		// Remove last node in path
		array_pop($path);
	}
	// Handles the request of find all all sorted path root to leaf nodes
	public	function allSortedPath()
	{
		// This is use to collect sort path
		$path = array();
		if ($this->root == NULL)
		{
			// Empty Tree
			return;
		}
		else
		{
			$this->sortPath($this->root, $path);
		}
	}
}

function main()
{
	// Create new binary tree
	$tree = new BinaryTree();
	/*
	         4                            
	       /   \    
	      4     7    
	     / \     \               
	    2   5     12
	       / \    / \
	      10  8  5   18
	     /        \
	    19         15 
	-----------------
	Constructing binary tree     
	*/
	$tree->root = new TreeNode(4);
	$tree->root->left = new TreeNode(4);
	$tree->root->left->right = new TreeNode(5);
	$tree->root->left->right->left = new TreeNode(10);
	$tree->root->left->right->left->left = new TreeNode(19);
	$tree->root->left->right->right = new TreeNode(8);
	$tree->root->left->left = new TreeNode(2);
	$tree->root->right = new TreeNode(7);
	$tree->root->right->right = new TreeNode(12);
	$tree->root->right->right->right = new TreeNode(18);
	$tree->root->right->right->left = new TreeNode(5);
	$tree->root->right->right->left->right = new TreeNode(15);
	$tree->allSortedPath();
}
main();

input

 4 4 5 10 19
 4 4 5 8
 4 7 12 18
/*
    Node JS Program
    Print all sorted path from root to leaf in binary tree
*/
// Binary Tree node
class TreeNode
{
	constructor(data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	constructor()
	{
		this.root = null;
	}
	// Display given path
	printPath(path)
	{
		var i = 0;
		// print path
		while (i < path.length)
		{
			process.stdout.write(" " + path[i]);
			i++;
		}
		process.stdout.write("\n");
	}
	//  Find and print sorted path using recursion
	sortPath(node, path)
	{
		if (node == null)
		{
			return;
		}
		// Add path element
		path.push(node.data);
		if (node.left == null && node.right == null)
		{
			// Display calculated path
			this.printPath(path);
		}
		else
		{
			if (node.left != null && node.left.data >= node.data)
			{
				// When left node exists and its is ascending order
				this.sortPath(node.left, path);
			}
			if (node.right != null && node.right.data >= node.data)
			{
				// When right node exists and its is ascending order
				this.sortPath(node.right, path);
			}
		}
		// Remove last node in path
		path.pop();
	}
	// Handles the request of find all all sorted path root to leaf nodes
	allSortedPath()
	{
		// This is use to collect sort path
		var path = [];
		if (this.root == null)
		{
			// Empty Tree
			return;
		}
		else
		{
			this.sortPath(this.root, path);
		}
	}
}

function main()
{
	// Create new binary tree
	var tree = new BinaryTree();
	/*
	         4                            
	       /   \    
	      4     7    
	     / \     \               
	    2   5     12
	       / \    / \
	      10  8  5   18
	     /        \
	    19         15 
	-----------------
	Constructing binary tree     
	*/
	tree.root = new TreeNode(4);
	tree.root.left = new TreeNode(4);
	tree.root.left.right = new TreeNode(5);
	tree.root.left.right.left = new TreeNode(10);
	tree.root.left.right.left.left = new TreeNode(19);
	tree.root.left.right.right = new TreeNode(8);
	tree.root.left.left = new TreeNode(2);
	tree.root.right = new TreeNode(7);
	tree.root.right.right = new TreeNode(12);
	tree.root.right.right.right = new TreeNode(18);
	tree.root.right.right.left = new TreeNode(5);
	tree.root.right.right.left.right = new TreeNode(15);
	tree.allSortedPath();
}
main();

input

 4 4 5 10 19
 4 4 5 8
 4 7 12 18
#    Python 3 Program
#    Print all sorted path from root to leaf in binary tree

#  Binary Tree node
class TreeNode :
	def __init__(self, data) :
		#  Set node value
		self.data = data
		self.left = None
		self.right = None
	

class BinaryTree :
	def __init__(self) :
		self.root = None
	
	#  Display given path
	def printPath(self, path) :
		i = 0
		#  print path
		while (i < len(path)) :
			print(" ", path[i], end = "")
			i += 1
		
		print(end = "\n")
	
	#   Find and print sorted path using recursion
	def sortPath(self, node, path) :
		if (node == None) :
			return
		
		#  Add path element
		path.append(node.data)
		if (node.left == None and node.right == None) :
			#  Display calculated path
			self.printPath(path)
		else :
			if (node.left != None and node.left.data >= node.data) :
				#  When left node exists and its is ascending order
				self.sortPath(node.left, path)
			
			if (node.right != None and node.right.data >= node.data) :
				#  When right node exists and its is ascending order
				self.sortPath(node.right, path)
			
		
		#  Remove last node in path
		del path[len(path) - 1]
	
	#  Handles the request of find all all sorted path root to leaf nodes
	def allSortedPath(self) :
		#  This is use to collect sort path
		path = []
		if (self.root == None) :
			#  Empty Tree
			return
		else :
			self.sortPath(self.root, path)
		
	

def main() :
	#  Create new binary tree
	tree = BinaryTree()
	#         4                            
	#       /   \    
	#      4     7    
	#     / \     \               
	#    2   5     12
	#       / \    / \
	#      10  8  5   18
	#     /        \
	#    19         15 
	# -----------------
	# Constructing binary tree     
	tree.root = TreeNode(4)
	tree.root.left = TreeNode(4)
	tree.root.left.right = TreeNode(5)
	tree.root.left.right.left = TreeNode(10)
	tree.root.left.right.left.left = TreeNode(19)
	tree.root.left.right.right = TreeNode(8)
	tree.root.left.left = TreeNode(2)
	tree.root.right = TreeNode(7)
	tree.root.right.right = TreeNode(12)
	tree.root.right.right.right = TreeNode(18)
	tree.root.right.right.left = TreeNode(5)
	tree.root.right.right.left.right = TreeNode(15)
	tree.allSortedPath()

if __name__ == "__main__": main()

input

  4  4  5  10  19
  4  4  5  8
  4  7  12  18
#    Ruby Program
#    Print all sorted path from root to leaf in binary tree

#  Binary Tree node
class TreeNode 
	# Define the accessor and reader of class TreeNode
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(data) 
		#  Set node value
		self.data = data
		self.left = nil
		self.right = nil
	end

end

class BinaryTree 
	# Define the accessor and reader of class BinaryTree
	attr_reader :root
	attr_accessor :root
	def initialize() 
		self.root = nil
	end

	#  Display given path
	def printPath(path) 
		i = 0
		#  print path
		while (i < path.length) 
			print(" ", path[i])
			i += 1
		end

		print("\n")
	end

	#   Find and print sorted path using recursion
	def sortPath(node, path) 
		if (node == nil) 
			return
		end

		#  Add path element
		path.push(node.data)
		if (node.left == nil && node.right == nil) 
			#  Display calculated path
			self.printPath(path)
 		else 
			if (node.left != nil && node.left.data >= node.data) 
				#  When left node exists and its is ascending order
				self.sortPath(node.left, path)
			end

			if (node.right != nil && node.right.data >= node.data) 
				#  When right node exists and its is ascending order
				self.sortPath(node.right, path)
			end

		end

		#  Remove last node in path
		path.delete_at(path.length - 1)
	end

	#  Handles the request of find all all sorted path root to leaf nodes
	def allSortedPath() 
		#  This is use to collect sort path
		path = []
		if (self.root == nil) 
			#  Empty Tree
			return
 		else 
			self.sortPath(self.root, path)
		end

	end

end

def main() 
	#  Create new binary tree
	tree = BinaryTree.new()
	#         4                            
	#       /   \    
	#      4     7    
	#     / \     \               
	#    2   5     12
	#       / \    / \
	#      10  8  5   18
	#     /        \
	#    19         15 
	# -----------------
	# Constructing binary tree     
	tree.root = TreeNode.new(4)
	tree.root.left = TreeNode.new(4)
	tree.root.left.right = TreeNode.new(5)
	tree.root.left.right.left = TreeNode.new(10)
	tree.root.left.right.left.left = TreeNode.new(19)
	tree.root.left.right.right = TreeNode.new(8)
	tree.root.left.left = TreeNode.new(2)
	tree.root.right = TreeNode.new(7)
	tree.root.right.right = TreeNode.new(12)
	tree.root.right.right.right = TreeNode.new(18)
	tree.root.right.right.left = TreeNode.new(5)
	tree.root.right.right.left.right = TreeNode.new(15)
	tree.allSortedPath()
end

main()

input

 4 4 5 10 19
 4 4 5 8
 4 7 12 18
import scala.collection.mutable._;
/*
    Scala Program
    Print all sorted path from root to leaf in binary tree
*/
// Binary Tree node
class TreeNode(var data: Int,
	var left: TreeNode,
		var right: TreeNode)
{
	def this(data: Int)
	{
		// Set node value
		this(data,null,null);
	}
}
class BinaryTree(var root: TreeNode)
{
	def this()
	{
		this(null);
	}
	// Display given path
	def printPath(path: ArrayBuffer[Int]): Unit = {
		var i: Int = 0;
		// print path
		while (i < path.size)
		{
			print(" " + path(i));
			i += 1;
		}
		print("\n");
	}
	//  Find and print sorted path using recursion
	def sortPath(node: TreeNode, path: ArrayBuffer[Int]): Unit = {
		if (node == null)
		{
			return;
		}
		// Add path element
		path += node.data;
		if (node.left == null && node.right == null)
		{
			// Display calculated path
			printPath(path);
		}
		else
		{
			if (node.left != null && node.left.data >= node.data)
			{
				// When left node exists and its is ascending order
				sortPath(node.left, path);
			}
			if (node.right != null && node.right.data >= node.data)
			{
				// When right node exists and its is ascending order
				sortPath(node.right, path);
			}
		}
		// Remove last node in path
		path.remove(path.size - 1);
	}
	// Handles the request of find all all sorted path root to leaf nodes
	def allSortedPath(): Unit = {
		// This is use to collect sort path
		var path: ArrayBuffer[Int] = new ArrayBuffer[Int]();
		if (this.root == null)
		{
			// Empty Tree
			return;
		}
		else
		{
			sortPath(this.root, path);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create new binary tree
		var tree: BinaryTree = new BinaryTree();
		/*
		         4                            
		       /   \    
		      4     7    
		     / \     \               
		    2   5     12
		       / \    / \
		      10  8  5   18
		     /        \
		    19         15 
		-----------------
		Constructing binary tree     
		*/
		tree.root = new TreeNode(4);
		tree.root.left = new TreeNode(4);
		tree.root.left.right = new TreeNode(5);
		tree.root.left.right.left = new TreeNode(10);
		tree.root.left.right.left.left = new TreeNode(19);
		tree.root.left.right.right = new TreeNode(8);
		tree.root.left.left = new TreeNode(2);
		tree.root.right = new TreeNode(7);
		tree.root.right.right = new TreeNode(12);
		tree.root.right.right.right = new TreeNode(18);
		tree.root.right.right.left = new TreeNode(5);
		tree.root.right.right.left.right = new TreeNode(15);
		tree.allSortedPath();
	}
}

input

 4 4 5 10 19
 4 4 5 8
 4 7 12 18
import Foundation;
/*
    Swift 4 Program
    Print all sorted path from root to leaf in binary tree
*/
// Binary Tree node
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		// Set node value
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class BinaryTree
{
	var root: TreeNode? ;
	init()
	{
		self.root = nil;
	}
	// Display given path
	func printPath(_ path: [Int])
	{
		var i = 0;
		// print path
		while (i < path.count)
		{
			print(" ", path[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	//  Find and print sorted path using recursion
	func sortPath(_ node: TreeNode? , _ path : inout[Int])
	{
		if (node == nil)
		{
			return;
		}
		// Add path element
		path.append(node!.data);
		if (node!.left == nil && node!.right == nil)
		{
			// Display calculated path
			self.printPath(path);
		}
		else
		{
			if (node!.left  != nil && node!.left!.data >= node!.data)
			{
				// When left node exists and its is ascending order
				self.sortPath(node!.left, &path);
			}
			if (node!.right  != nil && node!.right!.data >= node!.data)
			{
				// When right node exists and its is ascending order
				self.sortPath(node!.right, &path);
			}
		}
		// Remove last node in path
		path.removeLast();
	}
	// Handles the request of find all all sorted path root to leaf nodes
	func allSortedPath()
	{
		// This is use to collect sort path
		var path = [Int]();
		if (self.root == nil)
		{
			// Empty Tree
			return;
		}
		else
		{
			self.sortPath(self.root, &path);
		}
	}
}
func main()
{
	// Create new binary tree
	let tree = BinaryTree();
	/*
	         4                            
	       /   \    
	      4     7    
	     / \     \               
	    2   5     12
	       / \    / \
	      10  8  5   18
	     /        \
	    19         15 
	-----------------
	Constructing binary tree     
	*/
	tree.root = TreeNode(4);
	tree.root!.left = TreeNode(4);
	tree.root!.left!.right = TreeNode(5);
	tree.root!.left!.right!.left = TreeNode(10);
	tree.root!.left!.right!.left!.left = TreeNode(19);
	tree.root!.left!.right!.right = TreeNode(8);
	tree.root!.left!.left = TreeNode(2);
	tree.root!.right = TreeNode(7);
	tree.root!.right!.right = TreeNode(12);
	tree.root!.right!.right!.right = TreeNode(18);
	tree.root!.right!.right!.left = TreeNode(5);
	tree.root!.right!.right!.left!.right = TreeNode(15);
	tree.allSortedPath();
}
main();

input

  4  4  5  10  19
  4  4  5  8
  4  7  12  18
/*
    Kotlin Program
    Print all sorted path from root to leaf in binary tree
*/
// Binary Tree node
class TreeNode
{
	var data: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Int)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	var root: TreeNode ? ;
	constructor()
	{
		this.root = null;
	}
	// Display given path
	fun printPath(path: MutableList<Int> ): Unit
	{
		var i: Int = 0;
		// print path
		while (i < path.size)
		{
			print(" " + path[i]);
			i += 1;
		}
		print("\n");
	}
	//  Find and print sorted path using recursion
	fun sortPath(node: TreeNode ? , path : MutableList<Int> ): Unit
	{
		if (node == null)
		{
			return;
		}
		// Add path element
		path.add(node.data);
		if (node.left == null && node.right == null)
		{
			// Display calculated path
			this.printPath(path);
		}
		else
		{
			if (node.left != null && node.left!!.data >= node.data)
			{
				// When left node exists and its is ascending order
				this.sortPath(node.left, path);
			}
			if (node.right != null && node.right!!.data >= node.data)
			{
				// When right node exists and its is ascending order
				this.sortPath(node.right, path);
			}
		}
		// Remove last node in path
		path.removeAt(path.size - 1);
	}
	// Handles the request of find all all sorted path root to leaf nodes
	fun allSortedPath(): Unit
	{
		// This is use to collect sort path
		var path = mutableListOf<Int>();
		if (this.root == null)
		{
			// Empty Tree
			return;
		}
		else
		{
			this.sortPath(this.root, path);
		}
	}
}
fun main(args: Array < String > ): Unit
{
	// Create new binary tree
	val tree: BinaryTree = BinaryTree();
	/*
	         4                            
	       /   \    
	      4     7    
	     / \     \               
	    2   5     12
	       / \    / \
	      10  8  5   18
	     /        \
	    19         15 
	-----------------
	Constructing binary tree     
	*/
	tree.root = TreeNode(4);
	tree.root?.left = TreeNode(4);
	tree.root?.left?.right = TreeNode(5);
	tree.root?.left?.right?.left = TreeNode(10);
	tree.root?.left?.right?.left?.left = TreeNode(19);
	tree.root?.left?.right?.right = TreeNode(8);
	tree.root?.left?.left = TreeNode(2);
	tree.root?.right = TreeNode(7);
	tree.root?.right?.right = TreeNode(12);
	tree.root?.right?.right?.right = TreeNode(18);
	tree.root?.right?.right?.left = TreeNode(5);
	tree.root?.right?.right?.left?.right = TreeNode(15);
	tree.allSortedPath();
}

input

 4 4 5 10 19
 4 4 5 8
 4 7 12 18

Time Complexity

The time complexity of the solution is mainly determined by the number of nodes in the binary tree and the number of paths that satisfy the ascending order condition. In the worst case, we would traverse all paths from the root to the leaf nodes, which would result in a time complexity of O(n), where n is the number of nodes in the binary tree.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment