Posted on by Kalkicode
Code Recursion

Find the first Sorted path in binary tree

The problem involves finding the first sorted path in a binary tree. A sorted path is a path in which the values of nodes encountered along the path are in non-decreasing order. The task is to identify and print the first sorted path from the root to a leaf node in the binary tree.

Problem Statement

Given a binary tree, the goal is to find and print the first sorted path from the root node to a leaf node.

Example

Consider the following binary tree:


          4
        /   \
       4     7
      / \     \
     2   5     12
        / \    /
       10  8  5
      /       \
     9         15

In this example, the first sorted path is [4, 4, 5, 8], which is the path from the root node to the leaf node with value 8.

Idea to Solve

The problem can be approached using a recursive depth-first traversal of the binary tree. While traversing, we check if the current node value is greater than or equal to the previous node value. If it is, we continue down the path. If it's not, we backtrack and explore other branches.

Program Solution

import java.util.ArrayList;
/*
    Java Program
    Find the first Sorted path 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++;
		}
	}
	public boolean sortPath(TreeNode node, ArrayList < Integer > path)
	{
		if (node == null)
		{
			return false;
		}
		// Add path element
		path.add(node.data);
		if (node.left == null && node.right == null)
		{
			// When the node is a leaf node then stop the process
			// Because we have get the resulting path
			return true;
		}
		if (node.left != null && node.left.data >= node.data 
            && (sortPath(node.left, path)))
		{
			return true;
		}
		if (node.right != null && node.right.data >= node.data 
            && sortPath(node.right, path))
		{
			return true;
		}
		// Remove last path node
		path.remove(path.size() - 1);
		return false;
	}
	// Handles the request to find first sorted path in binary tree
	public void firstSortedPath()
	{
		// This is use to collect sort path
		ArrayList < Integer > path = new ArrayList < Integer > ();
		if (this.root == null)
		{
			// Empty Tree
			return;
		}
		else
		{
			// Collecting first sorted path when exists
			sortPath(this.root, path);
		}
		if (path.size() == 0)
		{
			// When there is no sort path in binary tree
			System.out.print("None");
		}
		else
		{
			printPath(path);
		}
	}
	public static void main(String[] args)
	{
		// Create new binary tree
		BinaryTree tree = new BinaryTree();
		/*
		         4                            
		       /   \    
		      4     7    
		     / \     \               
		    2   5     12
		       / \    / 
		      10  8  5
		      /       \
		     9         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(9);
		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.left = new TreeNode(5);
		tree.root.right.right.left.right = new TreeNode(15);
		// Test case
		tree.firstSortedPath();
	}
}

input

 4 4 5 8
// Include header file
#include <iostream>
#include <vector>
using namespace std;
/*
    C++ Program
    Find the first Sorted path 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++;
		}
	}
	bool sortPath(TreeNode *node, vector < int > &path)
	{
		if (node == NULL)
		{
			return false;
		}
		// Add path element
		path.push_back(node->data);
		if (node->left == NULL && node->right == NULL)
		{
			// When the node is a leaf node then stop the process
			// Because we have get the resulting path
			return true;
		}
		if (node->left != NULL && node->left->data >= node->data 
            && (this->sortPath(node->left, path)))
		{
			return true;
		}
		if (node->right != NULL && node->right->data >= node->data 
            && this->sortPath(node->right, path))
		{
			return true;
		}
		// Remove last path node
		path.pop_back();
		return false;
	}
	// Handles the request to find first sorted path in binary tree
	void firstSortedPath()
	{
		// This is use to collect sort path
		vector < int > path;
		if (this->root == NULL)
		{
			// Empty Tree
			return;
		}
		else
		{
			// Collecting first sorted path when exists
			this->sortPath(this->root, path);
		}
		if (path.size() == 0)
		{
			// When there is no sort path in binary tree
			cout << "None";
		}
		else
		{
			this->printPath(path);
		}
	}
};
int main()
{
	// Create new binary tree
	BinaryTree *tree = new BinaryTree();
	/*
	         4                            
	       /   \    
	      4     7    
	     / \     \               
	    2   5     12
	       / \    / 
	      10  8  5
	      /       \
	     9         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(9);
	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->left = new TreeNode(5);
	tree->root->right->right->left->right = new TreeNode(15);
	// Test case
	tree->firstSortedPath();
	return 0;
}

input

 4 4 5 8
// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp Program
    Find the first Sorted path 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++;
		}
	}
	public Boolean sortPath(TreeNode node, List < int > path)
	{
		if (node == null)
		{
			return false;
		}
		// Add path element
		path.Add(node.data);
		if (node.left == null && node.right == null)
		{
			// When the node is a leaf node then stop the process
			// Because we have get the resulting path
			return true;
		}
		if (node.left != null && node.left.data >= node.data 
            && (this.sortPath(node.left, path)))
		{
			return true;
		}
		if (node.right != null && node.right.data >= node.data 
            && this.sortPath(node.right, path))
		{
			return true;
		}
		// Remove last path node
		path.RemoveAt(path.Count - 1);
		return false;
	}
	// Handles the request to find first sorted path in binary tree
	public void firstSortedPath()
	{
		// This is use to collect sort path
		List < int > path = new List < int > ();
		if (this.root == null)
		{
			// Empty Tree
			return;
		}
		else
		{
			// Collecting first sorted path when exists
			this.sortPath(this.root, path);
		}
		if (path.Count == 0)
		{
			// When there is no sort path in binary tree
			Console.Write("None");
		}
		else
		{
			this.printPath(path);
		}
	}
	public static void Main(String[] args)
	{
		// Create new binary tree
		BinaryTree tree = new BinaryTree();
		/*
		         4                            
		       /   \    
		      4     7    
		     / \     \               
		    2   5     12
		       / \    / 
		      10  8  5
		      /       \
		     9         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(9);
		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.left = new TreeNode(5);
		tree.root.right.right.left.right = new TreeNode(15);
		// Test case
		tree.firstSortedPath();
	}
}

input

 4 4 5 8
<?php
/*
    Php Program
    Find the first Sorted path 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++;
		}
	}
	public	function sortPath($node, &$path)
	{
		if ($node == NULL)
		{
			return false;
		}
		// Add path element
		$path[] = $node->data;
		if ($node->left == NULL && $node->right == NULL)
		{
			// When the node is a leaf node then stop the process
			// Because we have get the resulting path
			return true;
		}
		if ($node->left != NULL && $node->left->data >= $node->data 
            && ($this->sortPath($node->left, $path)))
		{
			return true;
		}
		if ($node->right != NULL && $node->right->data >= $node->data 
            && $this->sortPath($node->right, $path))
		{
			return true;
		}
		// Remove last path node
		array_pop($path);
		return false;
	}
	// Handles the request to find first sorted path in binary tree
	public	function firstSortedPath()
	{
		// This is use to collect sort path
		$path = array();
		if ($this->root == NULL)
		{
			// Empty Tree
			return;
		}
		else
		{
			// Collecting first sorted path when exists
			$this->sortPath($this->root, $path);
		}
		if (count($path) == 0)
		{
			// When there is no sort path in binary tree
			echo("None");
		}
		else
		{
			$this->printPath($path);
		}
	}
}

function main()
{
	// Create new binary tree
	$tree = new BinaryTree();
	/*
	         4                            
	       /   \    
	      4     7    
	     / \     \               
	    2   5     12
	       / \    / 
	      10  8  5
	      /       \
	     9         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(9);
	$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->left = new TreeNode(5);
	$tree->root->right->right->left->right = new TreeNode(15);
	// Test case
	$tree->firstSortedPath();
}
main();

input

 4 4 5 8
/*
    Node JS Program
    Find the first Sorted path 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++;
		}
	}
	sortPath(node, path)
	{
		if (node == null)
		{
			return false;
		}
		// Add path element
		path.push(node.data);
		if (node.left == null && node.right == null)
		{
			// When the node is a leaf node then stop the process
			// Because we have get the resulting path
			return true;
		}
		if (node.left != null && node.left.data >= node.data 
            && (this.sortPath(node.left, path)))
		{
			return true;
		}
		if (node.right != null && node.right.data >= node.data 
            && this.sortPath(node.right, path))
		{
			return true;
		}
		// Remove last path node
		path.pop();
		return false;
	}
	// Handles the request to find first sorted path in binary tree
	firstSortedPath()
	{
		// This is use to collect sort path
		var path = [];
		if (this.root == null)
		{
			// Empty Tree
			return;
		}
		else
		{
			// Collecting first sorted path when exists
			this.sortPath(this.root, path);
		}
		if (path.length == 0)
		{
			// When there is no sort path in binary tree
			process.stdout.write("None");
		}
		else
		{
			this.printPath(path);
		}
	}
}

function main()
{
	// Create new binary tree
	var tree = new BinaryTree();
	/*
	         4                            
	       /   \    
	      4     7    
	     / \     \               
	    2   5     12
	       / \    / 
	      10  8  5
	      /       \
	     9         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(9);
	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.left = new TreeNode(5);
	tree.root.right.right.left.right = new TreeNode(15);
	// Test case
	tree.firstSortedPath();
}
main();

input

 4 4 5 8
#    Python 3 Program
#    Find the first Sorted path 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
		
	
	def sortPath(self, node, path) :
		if (node == None) :
			return False
		
		#  Add path element
		path.append(node.data)
		if (node.left == None and node.right == None) :
			#  When the node is a leaf node then stop the process
			#  Because we have get the resulting path
			return True
		
		if (node.left != None and node.left.data >= node.data and 
            (self.sortPath(node.left, path))) :
			return True
		
		if (node.right != None and node.right.data >= node.data and 
            self.sortPath(node.right, path)) :
			return True
		
		#  Remove last path node
		del path[len(path) - 1]
		return False
	
	#  Handles the request to find first sorted path in binary tree
	def firstSortedPath(self) :
		#  This is use to collect sort path
		path = []
		if (self.root == None) :
			#  Empty Tree
			return
		else :
			#  Collecting first sorted path when exists
			self.sortPath(self.root, path)
		
		if (len(path) == 0) :
			#  When there is no sort path in binary tree
			print("None", end = "")
		else :
			self.printPath(path)
		
	

def main() :
	#  Create new binary tree
	tree = BinaryTree()
	#         4                            
	#       /   \    
	#      4     7    
	#     / \     \               
	#    2   5     12
	#       / \    / 
	#      10  8  5
	#      /       \
	#     9         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(9)
	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.left = TreeNode(5)
	tree.root.right.right.left.right = TreeNode(15)
	#  Test case
	tree.firstSortedPath()

if __name__ == "__main__": main()

input

  4  4  5  8
#    Ruby Program
#    Find the first Sorted path 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

	end

	def sortPath(node, path) 
		if (node == nil) 
			return false
		end

		#  Add path element
		path.push(node.data)
		if (node.left == nil && node.right == nil) 
			#  When the node is a leaf node then stop the process
			#  Because we have get the resulting path
			return true
		end

		if (node.left != nil && node.left.data >= node.data && (self.sortPath(node.left, path))) 
			return true
		end

		if (node.right != nil && node.right.data >= node.data && self.sortPath(node.right, path)) 
			return true
		end

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

	#  Handles the request to find first sorted path in binary tree
	def firstSortedPath() 
		#  This is use to collect sort path
		path = []
		if (self.root == nil) 
			#  Empty Tree
			return
 		else 
			#  Collecting first sorted path when exists
			self.sortPath(self.root, path)
		end

		if (path.length == 0) 
			#  When there is no sort path in binary tree
			print("None")
 		else 
			self.printPath(path)
		end

	end

end

def main() 
	#  Create new binary tree
	tree = BinaryTree.new()
	#         4                            
	#       /   \    
	#      4     7    
	#     / \     \               
	#    2   5     12
	#       / \    / 
	#      10  8  5
	#      /       \
	#     9         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(9)
	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.left = TreeNode.new(5)
	tree.root.right.right.left.right = TreeNode.new(15)
	#  Test case
	tree.firstSortedPath()
end

main()

input

 4 4 5 8
import scala.collection.mutable._;
/*
    Scala Program
    Find the first Sorted path 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;
		}
	}
	def sortPath(node: TreeNode, path: ArrayBuffer[Int]): Boolean = {
		if (node == null)
		{
			return false;
		}
		// Add path element
		path += node.data;
		if (node.left == null && node.right == null)
		{
			// When the node is a leaf node then stop the process
			// Because we have get the resulting path
			return true;
		}
		if (node.left != null && node.left.data >= node.data 
            && (sortPath(node.left, path)))
		{
			return true;
		}
		if (node.right != null && node.right.data >= node.data 
            && sortPath(node.right, path))
		{
			return true;
		}
		// Remove last path node
		path.remove(path.size - 1);
		return false;
	}
	// Handles the request to find first sorted path in binary tree
	def firstSortedPath(): Unit = {
		// This is use to collect sort path
		var path: ArrayBuffer[Int] = new ArrayBuffer[Int]();
		if (this.root == null)
		{
			// Empty Tree
			return;
		}
		else
		{
			// Collecting first sorted path when exists
			sortPath(this.root, path);
		}
		if (path.size == 0)
		{
			// When there is no sort path in binary tree
			print("None");
		}
		else
		{
			printPath(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
		      /       \
		     9         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(9);
		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.left = new TreeNode(5);
		tree.root.right.right.left.right = new TreeNode(15);
		// Test case
		tree.firstSortedPath();
	}
}

input

 4 4 5 8
import Foundation;
/*
    Swift 4 Program
    Find the first Sorted path 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;
		}
	}
	func sortPath(_ node: TreeNode? , _ path : inout[Int]) -> Bool
	{
		if (node == nil)
		{
			return false;
		}
		// Add path element
		path.append(node!.data);
		if (node!.left == nil && node!.right == nil)
		{
			// When the node is a leaf node then stop the process
			// Because we have get the resulting path
			return true;
		}
		if (node!.left  != nil && node!.left!.data >= node!.data 
            && (self.sortPath(node!.left, &path)))
		{
			return true;
		}
		if (node!.right  != nil && node!.right!.data >= node!.data 
            && self.sortPath(node!.right, &path))
		{
			return true;
		}
		// Remove last path node
		path.removeLast();
		return false;
	}
	// Handles the request to find first sorted path in binary tree
	func firstSortedPath()
	{
		// This is use to collect sort path
		var path = [Int]();
		if (self.root == nil)
		{
			// Empty Tree
			return;
		}
		else
		{
			// Collecting first sorted path when exists
			let _ = self.sortPath(self.root, &path);
		}
		if (path.count == 0)
		{
			// When there is no sort path in binary tree
			print("None", terminator: "");
		}
		else
		{
			self.printPath(path);
		}
	}
}
func main()
{
	// Create new binary tree
	let tree = BinaryTree();
	/*
	         4                            
	       /   \    
	      4     7    
	     / \     \               
	    2   5     12
	       / \    / 
	      10  8  5
	      /       \
	     9         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(9);
	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!.left = TreeNode(5);
	tree.root!.right!.right!.left!.right = TreeNode(15);
	// Test case
	tree.firstSortedPath();
}
main();

input

  4  4  5  8
/*
    Kotlin Program
    Find the first Sorted path 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;
		}
	}
	fun sortPath(node: TreeNode ? , path :  MutableList<Int>  ): Boolean
	{
		if (node == null)
		{
			return false;
		}
		// Add path element
		path.add(node.data);
		if (node.left == null && node.right == null)
		{
			// When the node is a leaf node then stop the process
			// Because we have get the resulting path
			return true;
		}
		if (node.left != null && node.left!!.data >= node.data 
            && (this.sortPath(node.left, path)))
		{
			return true;
		}
		if (node.right != null && node.right!!.data >= node.data 
            && this.sortPath(node.right, path))
		{
			return true;
		}
		// Remove last path node
		path.removeAt(path.size - 1);
		return false;
	}
	// Handles the request to find first sorted path in binary tree
	fun firstSortedPath(): Unit
	{
		// This is use to collect sort path
		var path = mutableListOf<Int>();
		if (this.root == null)
		{
			// Empty Tree
			return;
		}
		else
		{
			// Collecting first sorted path when exists
			this.sortPath(this.root, path);
		}
		if (path.size == 0)
		{
			// When there is no sort path in binary tree
			print("None");
		}
		else
		{
			this.printPath(path);
		}
	}
}
fun main(args: Array < String > ): Unit
{
	// Create new binary tree
	val tree: BinaryTree = BinaryTree();
	/*
	         4                            
	       /   \    
	      4     7    
	     / \     \               
	    2   5     12
	       / \    / 
	      10  8  5
	      /       \
	     9         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(9);
	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?.left = TreeNode(5);
	tree.root?.right?.right?.left?.right = TreeNode(15);
	// Test case
	tree.firstSortedPath();
}

input

 4 4 5 8

Time Complexity

The algorithm traverses the binary tree in a depth-first manner, visiting each node once. Therefore, the time complexity is 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





Categories
Relative Post