forked from HarshCasper/NeoAlgo
-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathTrimming_binary_tree.java
More file actions
113 lines (99 loc) · 3.05 KB
/
Trimming_binary_tree.java
File metadata and controls
113 lines (99 loc) · 3.05 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/*
Trimming Binary Tree
You are given root of the binary search tree
and the low and high points, your task is to trim the tree
so that all its elements lies in low to high range only.
Trimmimg the tree should not change the relative structure
of the elements which will remain in the treeYou need to
return the root of the trimmed binary search tree.
Note that the root may change depending on the given bounds.
*/
import java.io.*;
import java.util.Scanner;
import java.util.*;
//defining a class for storing nodes of tree
class BTNode
{
int value;
BTNode left;
BTNode right;
BTNode()
{}
BTNode(int value)
{
this.value = value;
}
BTNode(int value, BTNode left, BTNode right)
{
this.value = value;
this.left = left;
this.right = right;
}
}
public class Trimming_binary_tree
{
//function to trim the binary tree
public BTNode trimBinaryTree(BTNode root, int low, int high)
{
//we use recursive approach
//if the root is empty then the root itself is returned
if (root == null)
{
return root;
}
//when BTNode.value will be greater than high
//then we know that the trimmed binary tree
//would occur to the eft of the node.
if (root.value > high)
{
return trimBinaryTree(root.left, low, high);
}
//similarly, when BTNode.value will be less than
//low value, then the trimmed binary tree occurs
//on the right of the node.
if (root.value < low)
{
return trimBinaryTree(root.right, low, high);
}
//otherwise, we trim both the sides of the
//tree
root.left = trimBinaryTree(root.left, low, high);
root.right = trimBinaryTree(root.right, low, high);
//returning the trimmed root
return root;
}
//driver code
public static void main (String[] args) throws IOException
{
// Taking input
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the values of nodes for tree : ");
String str = br.readLine();
Node root = buildTree(str);
System.out.println("Enter the value of lower range : ");
int low = br.nextInt();
System.out.println("Enter the value of high range : ");
int high = br.nextInt();
//for output
System.out.println("Root of the trimmed binary tree is : ");
System.out.print(trimBinaryTree(root, low, high));
System.out.println(" ");
}
}
/*
EXAMPLE:-
Input--
Enter the values of nodes for tree : 3 0 4 null 2 null null 1
Enter the value of lower range : 1
Enter the value of high range : 3
Output--
Root of the trimmed binary tree is : 3 2 null 1
Input--
Enter the values of nodes for tree : 1
Enter the value of lower range : 1
Enter the value of high range : 2
Output--
Root of the trimmed binary tree is : 1
TIME COMPLEXITY --> O(N)
SPACE COMPLEXITY --> O(N) ; where N is the total number of nodes in the tree
*/