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;
}
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;
}
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;
}
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;
}
\$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;
}
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

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_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_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

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;
}
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;
}
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;
}
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.

Categories
Relative Post