Given a complete binary tree with values indexed from 1 to N and a key K. The task is to check whether a key exists in the tree or not. Print “true” if the key exists, otherwise print “false”.
Complete Binary Tree: A Binary Tree is a complete Binary Tree if all the levels are completely filled except possibly the last level and the last level has all keys as left as possible
Examples:
Input: K = 2
1 / \ 2 3 / \ / \ 4 5 6 7 / \ / 8 9 10Output: true
Input: K = 11
1 / \ 2 3 / \ / \ 4 5 6 7 / \ / 8 9 10Output: false
Naive Approach: The simplest approach would be to simply traverse the entire tree and check if the key exists in the tree or not.
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: The approach is based on the idea that the tree is a complete binary tree and the nodes are indexed from 1 to N starting from the top. So we can track down the path going from the root to the key if at all the key existed. Below are the steps:
- For a complete binary tree given node i, its children will be 2*i and 2*i + 1. Therefore, given node i, its parent node will be i/2.
- Iteratively find out the parent of the key until the root node of the tree is found, and store the steps in an array steps[] as -1 for left and 1 for right (Left means that the current node is the left child of its parent and right means the current node is the right child of its parent).
- Now transverse the tree according to the moves stored in the array steps[]. If the entire array is successfully transversed, it means that the key exists in the tree so print “True”, otherwise print “False”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Class containing left// and right child of current node// and key valueclass Node { public: int data; Node* left; Node* right; Node(int item) { data = item; left = NULL; right = NULL; }};// Function to store the// list of the directionsvector<int> findSteps(Node* root, int data){ vector<int> steps; // While the root is not found while (data != 1) { // If it is the right // child of its parent if (data / 2.0 > data / 2) { // Add right step (1) steps.push_back(1); } else { // Add left step (-1) steps.push_back(-1); } int parent = data / 2; // Repeat the same // for its parent data = parent; } // Reverse the steps list reverse(steps.begin(), steps.end()); // Return the steps return steps;}// Function to find// if the key is present or notbool findKey(Node* root, int data){ // Get the steps to be followed vector<int> steps = findSteps(root, data); // Taking one step at a time for (auto cur_step : steps) { // Go left if (cur_step == -1) { // If left child does // not exist return false if (root->left == NULL) return false; root = root->left; } // Go right else { // If right child does // not exist return false if (root->right == NULL) return false; root = root->right; } } // If the entire array of steps // has been successfully // traversed return true;}int main(){ /* Consider the following complete binary tree 1 / \ 2 3 / \ / \ 4 5 6 7 / \ / 8 9 10 */ Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); root->right->left = new Node(6); root->right->right = new Node(7); root->left->left->left = new Node(8); root->left->left->right = new Node(9); root->left->right->left = new Node(10); // Function Call cout<<boolalpha<<findKey(root, 7)<<endl;}// This code is contributed by Pushpesh Raj. |
Java
// Java program for the above approachimport java.util.*;import java.io.*;// Class containing left// and right child of current node// and key valueclass Node { int data; Node left, right; public Node(int item) { data = item; left = null; right = null; }}class Solution { // Function to store the // list of the directions public static ArrayList<Integer> findSteps(Node root, int data) { ArrayList<Integer> steps = new ArrayList<Integer>(); // While the root is not found while (data != 1) { // If it is the right // child of its parent if (data / 2.0 > data / 2) { // Add right step (1) steps.add(1); } else { // Add left step (-1) steps.add(-1); } int parent = data / 2; // Repeat the same // for its parent data = parent; } // Reverse the steps list Collections.reverse(steps); // Return the steps return steps; } // Function to find // if the key is present or not public static boolean findKey(Node root, int data) { // Get the steps to be followed ArrayList<Integer> steps = findSteps(root, data); // Taking one step at a time for (Integer cur_step : steps) { // Go left if (cur_step == -1) { // If left child does // not exist return false if (root.left == null) return false; root = root.left; } // Go right else { // If right child does // not exist return false if (root.right == null) return false; root = root.right; } } // If the entire array of steps // has been successfully // traversed return true; } public static void main(String[] args) { /* Consider the following complete binary tree 1 / \ 2 3 / \ / \ 4 5 6 7 / \ / 8 9 10 */ Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.left.left.left = new Node(8); root.left.left.right = new Node(9); root.left.right.left = new Node(10); // Function Call System.out.println(findKey(root, 7)); }} |
Python3
# Python program to implement above approach# Class containing left# and right child of current node# and key valueclass Node: def __init__(self,item): self.data = item self.left = None self.right = None # Function to store the# list of the directionsdef findSteps(root,data): steps = [] # While the root is not found while (data != 1): # If it is the right # child of its parent if (data / 2 > data // 2): # Add right step (1) steps.append(1) else: # Add left step (-1) steps.append(-1) parent = data // 2 # Repeat the same # for its parent data = parent # Reverse the steps list steps = steps[::-1] # Return the steps return steps# Function to find# if the key is present or notdef findKey(root,data): # Get the steps to be followed steps = findSteps(root, data) # Taking one step at a time for cur_step in steps: # Go left if (cur_step == -1): # If left child does # not exist return False if (root.left == None): return False root = root.left # Go right else: # If right child does # not exist return False if (root.right == None): return False root = root.right # If the entire array of steps # has been successfully # traversed return True# driver code# Consider the following complete binary tree# 1# / \# 2 3# / \ / \# 4 5 6 7# / \ /# 8 9 10# root = Node(1)root.left = Node(2)root.right = Node(3)root.left.left = Node(4)root.left.right = Node(5)root.right.left = Node(6)root.right.right = Node(7)root.left.left.left = Node(8)root.left.left.right = Node(9)root.left.right.left = Node(10)# Function Callprint(findKey(root, 7))# This code is contributed by shinjanpatra |
C#
// C# program for the above approachusing System;using System.Collections.Generic;// Class containing left// and right child of current node// and key valueclass Node{ public int data; public Node left, right; public Node(int item) { data = item; left = right = null; }}class Solution { // Function to store the // list of the directions public static List<int> findSteps(Node root, int data) { List<int> steps = new List<int>(); // While the root is not found while (data != 1) { // If it is the right // child of its parent if (data / 2.0 > data / 2) { // Add right step (1) steps.Add(1); } else { // Add left step (-1) steps.Add(-1); } int parent = data / 2; // Repeat the same // for its parent data = parent; } // Reverse the steps list steps.Reverse(); // Return the steps return steps; } // Function to find // if the key is present or not public static bool findKey(Node root, int data) { // Get the steps to be followed List<int> steps = findSteps(root, data); // Taking one step at a time foreach (int cur_step in steps) { // Go left if (cur_step == -1) { // If left child does // not exist return false if (root.left == null) return false; root = root.left; } // Go right else { // If right child does // not exist return false if (root.right == null) return false; root = root.right; } } // If the entire array of steps // has been successfully // traversed return true; } public static void Main() { /* Consider the following complete binary tree 1 / \ 2 3 / \ / \ 4 5 6 7 / \ / 8 9 10 */ Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.left.left.left = new Node(8); root.left.left.right = new Node(9); root.left.right.left = new Node(10); // Function Call Console.Write(findKey(root, 7)); }} |
Javascript
<script>// JavaScript program to implement above approach// Class containing left// and right child of current node// and key valueclass Node { constructor(item) { this.data = item; this.left = null; this.right = null; }}// Function to store the// list of the directionsfunction findSteps(root,data){ let steps = []; // While the root is not found while (data != 1) { // If it is the right // child of its parent if (data / 2 > Math.floor(data / 2)) { // Add right step (1) steps.push(1); } else { // Add left step (-1) steps.push(-1); } let parent = Math.floor(data / 2); // Repeat the same // for its parent data = parent; } // Reverse the steps list steps.reverse(); // Return the steps return steps;}// Function to find// if the key is present or notfunction findKey(root,data){ // Get the steps to be followed let steps = findSteps(root, data); // Taking one step at a time for (let cur_step of steps) { // Go left if (cur_step == -1) { // If left child does // not exist return false if (root.left == null) return false; root = root.left; } // Go right else { // If right child does // not exist return false if (root.right == null) return false; root = root.right; } } // If the entire array of steps // has been successfully // traversed return true;}// driver code/* Consider the following complete binary tree 1 / \ 2 3 / \ / \ 4 5 6 7 / \ / 8 9 10 */let root = new Node(1);root.left = new Node(2);root.right = new Node(3);root.left.left = new Node(4);root.left.right = new Node(5);root.right.left = new Node(6);root.right.right = new Node(7);root.left.left.left = new Node(8);root.left.left.right = new Node(9);root.left.right.left = new Node(10);// Function Calldocument.write(findKey(root, 7),"</br>");// This code is contributed by shinjanpatra</script> |
Output:
true
Time Complexity: O(logN)
Auxiliary Space: O(logN)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
