Hello guys, if you are wondering how to check if a given node exists in a given binary tree or not then you have come to the right place. I have been sharing a lot of binary tree-based programming interview questions in the past few articles. Earlier, we have solved how to find the maximum sum level in a given binary tree, how to find the lowest common ancestor, and how to find Kth smallest element, and in his article, we will solve another classical binary tree problem of search nodes. Bug, before finding if a node exists in a binary tree or not. It is good to
understand what is a binary tree and binary search tree and how to solve a binary tree-based coding problem.
What then is a Binary Tree? A Binary tree is a data structure in which each node can have at most two children. That is, each node in the binary tree will have data, left child and right child.
Trees are the non-linear data structure that stores data hierarchy. The tree is a collection of elements called nodes. Nodes are connected through edges and contain data. The first node of the tree is called the Root. Each node may or may not have a children node. The node which doesn't have any child node is called a leaf.
Below is the image of the Binary search tree, all the green circles are called nodes and they have at most two other nodes called children.
Fig 1.0 Binary Tree.
In the diagram above, The root node is node 8 as you can see, And it has two Children node 3 and node 10, left and right respectively. Node 3 also has two children nodes 1 and 6
Trees are the non-linear data structure that stores data hierarchy. The tree is a collection of elements called nodes. Nodes are connected through edges and contain data. The first node of the tree is called the Root. Each node may or may not have a children node. The node which doesn't have any child node is called a leaf.
Below is the image of the Binary search tree, all the green circles are called nodes and they have at most two other nodes called children.
Fig 1.0 Binary Tree.
In the diagram above, The root node is node 8 as you can see, And it has two Children node 3 and node 10, left and right respectively. Node 3 also has two children nodes 1 and 6
Node 6 has two
children, node 4 and node 7 respectively, And to the right side of node 8 which
is node 10, has just only one child, node 14, node 14 too has only one
child. Nodes 4, 7, and 13 are called leaves because they do not have
children.
Important things to note when determining is if a tree is a binary tree or not, which are :
A Binary search tree (I.e BST) is a type of binary tree. It can also be defined as a node-based binary tree. BST is also referred to as ‘Ordered Binary Tree’. The BST data structure is considered to be very efficient when compared to Arrays and Linked lists when it comes to insertion/deletion and searching of items.
Similarly, insertion and deletion operations are more efficient in Binary Search Tree. When we want to insert a new element, we roughly know in which subtree (left or right) we will insert the element.
Yeah, That’s the solution to the problem, Now let me walk you through the algorithm with a detailed explanation. I numbered the codes so you would understand which line I am referring to in particular, Let’s go!
If you check from line 1 to line 10, you would see that there are two classes there, The class “Node” was embedded in the class “Binary tree Search”.
Note: It is not compulsory to have it embedded, as you can also have it in a separate java file, They only just have to be in the same package so the classes can access themselves.
line 3 to line 5 are instance variables of the class “Node”
Line 6 to line 10 is the constructor where the instance variables are constructed.
From Line 13 to line 30, is where the implementation happens. Line 13 declared a method “Node exists” which takes in two parameters, Node, and key respectively. Afterward, a series of conditions are checked as we go about checking if the nodes with the key exist.
Line 16 returns false if the node is null, Line 18 returns true if the data in the node is the same as the parameter “key” given. And The program would end there because we have seen what we are looking for. But if not, The searching continues as other conditions stated below are checked.
Line 22 checks if presents in left sub-tree, if true. The program ends there, if not, it proceeds to check the right sub-tree and returns either true or false.
Line 32 is the main method and from line 34 nodes are been initialized with values starting from the root nodes, to its children and children’s children.
Line 43 initialized the key we are looking for to 6 and in line 44 the method was called to find the key and here is the output:
It was true because 6 was present in the node.
Important things to note when determining is if a tree is a binary tree or not, which are :
- All data in the nodes of the left sub-tree are lesser than the right.
- In the Children nodes, All data on the left are lesser than the right.
- All data in the nodes of the left sub-tree is lesser than the root
- All data in the nodes of the right sub-tree is greater than the root.
A Binary search tree (I.e BST) is a type of binary tree. It can also be defined as a node-based binary tree. BST is also referred to as ‘Ordered Binary Tree’. The BST data structure is considered to be very efficient when compared to Arrays and Linked lists when it comes to insertion/deletion and searching of items.
Similarly, insertion and deletion operations are more efficient in Binary Search Tree. When we want to insert a new element, we roughly know in which subtree (left or right) we will insert the element.
Java Program to check if a given node exists in a binary tree or not
Having understood the Binary tree Data structure, we would be solving a problem. The problem is to check whether a given node exists in a binary tree, if it exists, it should return true, if not it should return false.And, here is a complete Java Program which not implement binary tree but also solves this problem.
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 | public class BinaryNodeTree { // Binary tree node static class Node { int data; Node left; Node right; public Node(int data) { this.data = data; left = right = null; } }; // Function to traverse the tree in preorder // and check if the given node exists in it static boolean nodeExists(Node node, int key) { if (node == null) return false; if (node.data == key) return true; // then check left subtree / boolean node1 = nodeExists(node.left, key); // node found, no need to look further if (node1) return true; //if node is not found in left, // then check right the sub-tree / boolean node2 = nodeExists(node.right, key); if (node2) { return true; } return false; } // Driver Code public static void main(String[] args) { BinaryNodeTree.Node root = new BinaryNodeTree.Node(0); root.left = new BinaryNodeTree.Node(1); root.left.left = new BinaryNodeTree.Node(3); root.left.left.left = new BinaryNodeTree.Node(6); root.left.right = new BinaryNodeTree.Node(4); root.left.right.left = new BinaryNodeTree.Node(8); root.left.right.right = new BinaryNodeTree.Node(9); root.right = new BinaryNodeTree.Node(2); root.right.left = new BinaryNodeTree.Node(5); root.right.right = new BinaryNodeTree.Node(7); int key = 6; if (nodeExists(root, key)) System.out.println("true"); else System.out.println("false"); } } |
Yeah, That’s the solution to the problem, Now let me walk you through the algorithm with a detailed explanation. I numbered the codes so you would understand which line I am referring to in particular, Let’s go!
If you check from line 1 to line 10, you would see that there are two classes there, The class “Node” was embedded in the class “Binary tree Search”.
Note: It is not compulsory to have it embedded, as you can also have it in a separate java file, They only just have to be in the same package so the classes can access themselves.
line 3 to line 5 are instance variables of the class “Node”
Line 6 to line 10 is the constructor where the instance variables are constructed.
From Line 13 to line 30, is where the implementation happens. Line 13 declared a method “Node exists” which takes in two parameters, Node, and key respectively. Afterward, a series of conditions are checked as we go about checking if the nodes with the key exist.
Line 16 returns false if the node is null, Line 18 returns true if the data in the node is the same as the parameter “key” given. And The program would end there because we have seen what we are looking for. But if not, The searching continues as other conditions stated below are checked.
Line 22 checks if presents in left sub-tree, if true. The program ends there, if not, it proceeds to check the right sub-tree and returns either true or false.
Line 32 is the main method and from line 34 nodes are been initialized with values starting from the root nodes, to its children and children’s children.
Line 43 initialized the key we are looking for to 6 and in line 44 the method was called to find the key and here is the output:
Output
trueIt was true because 6 was present in the node.
That's all about how to check if a given node is present in a given binary tree or not in Java.
This is an important binary tree-based coding question and if you are serious about doing well
on the technical or coding interviews, you should practice more binary tree-based coding questions like this. If you need more questions you
can also ways check out the following resources
Other data structure and algorithms tutorials for Java Programmers
Other data structure and algorithms tutorials for Java Programmers
- Top 50 Java Programs from Coding Interviews (see here)
- 5 Free Data Structure and Algorithms Courses for Programmers (courses)
- How to remove an element from the array without using a third-party library (check here)
- How to implement the Quicksort algorithm in Java? (solution)
- How to check if a String is a Palindrome in Java? [solution]
- How to find the missing number in a sorted array in Java? [answer]
- 10 Algorithms Books Every Programmer Should Read (books)
- 10 Algorithm books Every Programmer Should Read (list)
- 5 Books to learn data structure and algorithms in Java? (books)
- 10 Free Data Structure and Algorithm Courses for Programmers (courses)
- 100+ Data Structure Coding Problems from Interviews (questions)
- How to print the Fibonacci series in Java without using Recursion? [solution]
- How to check if an integer is a power of two without using division or modulo operator?[hint]
- How to find all permutations of String in Java? [solution]
- Top 21 String coding interview questions (see here)
- How to find the largest and smallest number in an array in Java (read here)
- How to find two maximum numbers on an integer array in Java (check here)
If you have any suggestions to make this algorithm better, feel free to
suggest. The interviewer loves people who come up with their own
algorithms or give some touch to popular algorithms.
P. S. - If you want to improve your data structure and algorithms skills and you need resources then you can also take a look at my list of best data structure and algorithm courses for Java developers. It contains some best online courses from Udemy, Coursera, edX, and other resources for Java developers.
P. S. - If you want to improve your data structure and algorithms skills and you need resources then you can also take a look at my list of best data structure and algorithm courses for Java developers. It contains some best online courses from Udemy, Coursera, edX, and other resources for Java developers.
No comments:
Post a Comment
Feel free to comment, ask questions if you have any doubt.