In the domain of data structures, Binary Search Trees (BSTs) play a fundamental role in facilitating efficient search, insertion, and deletion operations. However, there are times when we need to navigate the tree to find the parent of a given node which can be useful for various tree-related operations. This article explores the problem of finding the parent of a node in a BST using Java and provides a solution.
1. What is a Binary Search Tree (BST)?
A Binary Search Tree is a binary tree where each node has at most two child nodes (left and right), and the key (or value) of nodes in the left subtree is less than the key of the node itself, and the key of nodes in the right subtree is greater than or equal to the key of the node itself.
1.1 Example Binary Search Tree
Consider the following example of a Binary Search Tree:
In this tree, the parent of node 7 would be node 5, the parent of node 13 would be node 15, and so on. Understanding how to find the parent of a node enables efficient manipulation and traversal within a Binary Search Tree.
1.2 Problem Overview
Given a Binary Search Tree (BST) and a specific node within it, the task is to find the parent of that node. This can be useful for various tree-related operations, such as deletion or restructuring.
1.3 Solution Approach
We can solve this problem by traversing the BST starting from the root node. During traversal, we compare the key of the target node with the keys of nodes in the tree to determine whether to move left or right. As we traverse, we keep track of the parent of the current node. When we find the target node, we return its parent.
2. Node Structure for BST in Java
To begin with, let’s define the structure of a node in our BST. Each node will have a key (value), a left child reference, and a right child reference. Here’s how we can implement this in Java:
public class TreeNode {
int key;
TreeNode left;
TreeNode right;
public TreeNode(int key) {
this.key = key;
this.left = null;
this.right = null;
}
}
The above code snippet defines a Java class named TreeNode, which represents a node in a binary tree. Each node has three properties: key, left, and right.
- The
keyproperty holds the value of the node. - The
leftproperty points to the left child node. - The
rightproperty points to the right child node.
The class includes a constructor public TreeNode(int key) that initializes a node with the given key value. By default, the left and right child references are set to null, indicating that the node initially has no children.
3. Finding the Parent of a Node in BST
To find the parent of a given node in a BST, we can utilize a recursive approach. We will define a method that takes the root of the tree and the node whose parent we want to find. Here’s a breakdown of the algorithm:
- Start from the Root: Begin traversal of the BST from the root node.
- Search for the Node: As we traverse the tree:
- If the node’s key matches the key we are searching for, we’ve found the node and can return its parent.
- If the key is less than the current node’s key, move to the left child.
- If the key is greater than or equal to the current node’s key, move to the right child.
- Tracking the Parent: During traversal, keep track of the parent of the current node.
- Return the Parent: Once the node is found, return its parent node.
The code snippet below shows an example of how to implement this in Java:
public static TreeNode findParent(TreeNode root, TreeNode node) {
if (root == null || root == node) {
return null; // No parent or node is root
}
TreeNode parent = null;
TreeNode current = root;
while (current != null) {
if (node.key current.key) {
parent = current;
current = current.right;
} else {
// Node found, return its parent
return parent;
}
}
return null; // Node not found in the tree
}
This code defines a static method findParent that takes two parameters: root, representing the root of a binary search tree (BST), and node, representing the node whose parent we want to find. The method traverses the BST starting from the root node.
- If the key of the target node is less than the current node’s key, the traversal moves to the left child.
- If the key of the target node is greater than the current node’s key, the traversal moves to the right child.
- If the key matches the key of the target node, the method returns the parent node.
If the target node is not found in the tree or is the root node, the method returns null.
3.1 Using the findParent Method
Now that we have defined the findParent method, let’s see how we can use it to find the parent of a node in a BST:
public static void main(String[] args) {
// Constructing a sample BST
TreeNode root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(7);
root.right.left = new TreeNode(13);
root.right.right = new TreeNode(18);
// Suppose we want to find the parent of node with key 7
TreeNode nodeToFind = root.left.right;
TreeNode parent = findParent(root, nodeToFind);
if (parent != null) {
System.out.println("Parent of node " + nodeToFind.key + " is " + parent.key);
} else {
System.out.println("Node " + nodeToFind.key + " is either root or not found in the tree.");
}
}
The provided main method constructs a sample Binary Search Tree (BST) with various nodes and their corresponding keys. Based on the structure of the provided BST, the output from running the code with an input of 7 is:
Parent of node 7 is 5
This output indicates that the parent of the node with key 7 is the node with key 5. Similarly, if we provide an input of 18 to the program, the output will be:
Parent of node 18 is 15
4. Conclusion
In this article, we explored how to find the parent of a node in a Binary Search Tree (BST) using Java. Understanding this concept is essential for various tree operations and can help in efficiently navigating and manipulating trees.
5. Download the Source Code
This was an article on how to find the parent of a Node in a Binary Search Tree with Java.
You can download the full source code of this example here: Find the Parent of a Node in a Binary Search Tree with Java
