Ancestors of a Node in Binary Search Tree
In this article, we will discuss the ancestors of a node in a Binary Search Tree in C++.
Binary Tree is a data structure:
A binary tree is a hierarchical data structure made up of nodes, each of which has a maximum of two child nodes—one on the left and one on the right. Each node in a binary tree has its binary tree structure, and these child nodes can be thought of as subtrees. Nodes without offspring are referred to as leaf nodes, and the top node of the tree is known as the root.
Nodes:
Nodes are a binary tree's basic building blocks. Each node has a value or piece of data and can have 0–1–2 child nodes. The data is frequently stored and arranged at nodes in binary trees. A common binary tree node representation in C++ can be implemented as a class containing data properties, a pointer to the left child, and a pointer to the right child.
class BinaryTreeNode { public: int data; BinaryTreeNode* left; BinaryTreeNode* right; BinaryTreeNode(int val) : data(val), left(nullptr), right(nullptr) {} };
Example:
Here is a high-level description of how to do this in C++:
#include <iostream> class BinaryTreeNode { public: int data; BinaryTreeNode* left; BinaryTreeNode* right; BinaryTreeNode(int val) : data(val), left(nullptr), right(nullptr) {} }; bool findAndPrintAncestors(BinaryTreeNode* root, int target) { if (root == nullptr) { return false; // Base case: If the root is null, the target was not found. } if (root->data == target) { return true; // Base case: If the target node is found, stop recursion. } // Check if the target node is in the left or right subtree. if (findAndPrintAncestors(root->left, target) || findAndPrintAncestors(root->right, target)) { std::cout << root->data << " "; return true; // Print current node as an ancestor and stop recursion. } return false; // If the target was not found in the subtree, return false. } int main() { // Create a sample binary tree (or you can read the tree structure from the user too). BinaryTreeNode* root = new BinaryTreeNode(1); root->left = new BinaryTreeNode(2); root->right = new BinaryTreeNode(3); root->left->left = new BinaryTreeNode(4); root->left->right = new BinaryTreeNode(5); root->right->left = new BinaryTreeNode(6); root->right->right = new BinaryTreeNode(7); int targetNodeValue; std::cout << "Enter the target node value: "; std::cin >> targetNodeValue; // Find and print ancestors of the target node using the recursive approach. std::cout << "Ancestors of " << targetNodeValue << " are: "; findAndPrintAncestors(root, targetNodeValue); return 0; }
Output:
Explanation:
In this example, the findAncestors function of C++ code recursively searches for the target node while keeping track of the ancestors along the way. The list of ancestors is printed once the target node has been located. This idea is helpful in a number of situations, including tracing the ancestry of nodes in a hierarchical data structure or figuring out the route from the root to a particular node in a binary tree.
Recursive Method:
A recursive technique is frequently the most natural and effective way to discover and print the ancestors of a particular node in a binary tree. The recursive procedure moves up the tree from the base to the target node while recording all ancestors it encounters. Let's talk about the C++ recursive function that will be utilized to complete this operation.
Example:
#include <iostream> class BinaryTreeNode { public: int data; BinaryTreeNode* left; BinaryTreeNode* right; BinaryTreeNode(int val) : data(val), left(nullptr), right(nullptr) {} }; bool findAndPrintAncestors(BinaryTreeNode* root, int target) { if (root == nullptr) { return false; // Base case: If the root is null, the target was not found. } if (root->data == target) { return true; // Base case: If the target node is found, stop recursion. } // Check if the target node is in the left or right subtree. if (findAndPrintAncestors(root->left, target) || findAndPrintAncestors(root->right, target)) { std::cout << root->data << " "; return true; // Print the current node as an ancestor and stop recursion. } return false; // If the target was not found in the subtree, return false. } // Function to build a binary tree from user input BinaryTreeNode* buildBinaryTree() { int value; std::cout << "Enter the value (or -1 for null) for the current node: "; std::cin >> value; if (value == -1) { return nullptr; } BinaryTreeNode* node = new BinaryTreeNode(value); node->left = buildBinaryTree(); node->right = buildBinaryTree(); return node; } int main() { std::cout << "Enter the structure of the binary tree:" << std::endl; BinaryTreeNode* root = buildBinaryTree(); int targetNodeValue; std::cout << "Enter the target node value: "; std::cin >> targetNodeValue; // Find and print ancestors of the target node using the recursive approach. std::cout << "Ancestors of " << targetNodeValue << " are: "; findAndPrintAncestors(root, targetNodeValue); return 0; }
Output:
Time Complexity:
In the worst-case situation, it is possible to analyse the time complexity of the algorithm for utilizing a recursive approach to locate the ancestors of a given node in a binary tree. The worst-case scenario is when we have to search through all of the nodes in the tree to identify the ancestors because the target node is either the root node or it is situated in the rightmost leaf of the tree.
The algorithm executes a recursive depth-first traverse of an N-node binary tree. The time complexity analysis is as follows:
- We carry out constant-time actions at each node, such as determining whether the node is null and contrasting the data at the node with the desired value. O(1) time is required for these operations.
- In the worst situation, we would have to climb the whole height of the tree if the target node was in the rightmost leaf of the tree. A balanced binary tree has a height of O(log N), and an imbalanced binary tree can have a height of O(N).
- The algorithm traverses from the root to the target node and then returns to the top to print the ancestors. This process necessitates two complete tree traversals. Considering all of these factors, we can express the worst-case time complexity as O(N), where N represents the total number of nodes in the binary tree. The worst-case complexity occurs when it is necessary to visit every node in the tree.
- The time complexity would be better in a balanced binary tree, typically O(log N), for balanced binary tree searches with a logarithmic height. The worst-case scenario, where the tree is fully imbalanced, has an O(N) time complexity because it requires linearly traversing every node.
It's vital to remember that the time complexity might vary based on the binary tree's structure and that, on average, it might be less difficult than the complexity in the worst-case scenario.