Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Input
2.2.
Output
2.3.
Explanation
3.
Solution Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
Implementation in C++
3.4.
Implementation in Java
3.5.
Implementation in Python
3.6.
Time Complexity
3.7.
Space Complexity
4.
Frequently Asked Questions
4.1.
What are the various different types of binary trees?
4.2.
What are the applications of binary trees?
4.3.
What is the difference between a leaf node and a root node?
4.4.
What are the various ways to navigate a binary tree?
4.5.
What is a binary tree pre-order traversal?
4.6.
What benefits and drawbacks do binary trees offer?
4.7.
What is the difference between a binary tree and a binary search tree?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check Whether Every Node of the Binary Tree has a Value K on itself or its any Immediate Neighbours

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Hey Ninjas! In this blog, we will discuss a problem based on Binary trees. A Binary Tree is a data structure where data is stored in a node, and each node has either two child nodes, one child node, or no child node. The three primary traversal techniques are preorderinorder, and postorder. A Binary tree is a widely asked data structure in programming contests and technical interviews.

Title image

This blog will discuss the approach to check whether every node of the binary tree has a value K on itself or its immediate neighbors. We will use the pre-order traversal approach to solve this problem.

Problem Statement

We are given a binary tree and an integer K in the question, and we will have to check whether every given tree node has a value K on itself or any of its immediate neighbors. If this condition is true for each binary tree node, then return true else, return false.

Input

K = 5

Input image

Output

True

Explanation

As we can observe, the above binary tree has three nodes: 5, 7, 6, and 5.

  • Root node 5 has a value equal to K, satisfying the given condition.
     
  • The left child of the root node with value 7 has its parent with value K, so it meets the given requirement.
     
  • The right child of the root node with value 6 has its parent with value K, so it satisfies the given condition.
     
  • Leaf node with value five has a value equal to K, so it meets the given requirement.
     

All the binary tree nodes satisfy the condition in the problem statement so that we will return the output as ‘true’.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Solution Approach

We need to traverse the tree and maintain a boolean check to find whether the given binary tree satisfies all three conditions we mentioned before. We will also need a variable ‘parent’ to keep track of each node’s parent. Initially, we will pass the check as True, and the parent will be passed as NULL for the traversal function.

We will traverse the tree using the pre-order traversal method, and while traversing the tree, we will check the following three conditions for each node we visit,

  1. If the current node has a value equal to K.
  2. If the parent of the current node has a value equal to K.
  3. If any child of the current node has a value equal to K.
     

If all three conditions become false for any node during the traversal, we mark the check variable as False. In the end, we return the check to the main function.

Algorithm

  1. Start preorder traversal of the tree with check = True, parent = NULL.
     
  2. Check whether the current node has value K. If not, check the following.
    1. Check if the left child is NULL or has the value K.
    2. Check if the right child is NULL or has the value K.
    3. Check if the parent is NULL or has the value K.
       
  3. Recur for the left subtree.
     
  4. Recur for the right subtree.
     
  5. Return check

Dry Run

  • 1st pass: Initially, our root is 5, and this binary tree node satisfies the condition as it has a value equal to K. So, our check will remain valid, and we will go on and recur for the left and right subtree.
Dry run image 1
  • 2nd pass: Our root is now 7, and this binary tree node satisfies the condition as its parent has a value equal to K. So, our check will remain true, and we will go on and recur for its left and right subtree.
Dry run image 2

 

  • 3rd pass: The left and right nodes of the current node 7 are null, and according to our base condition, if the value of the current node is NULL, return true. Hence, both null nodes will return true.
Dry run image 3
  • 4th pass: Now, as the whole left subtree of root node 5 has recurred, so now it’s time to check for the right subtree of root node 5.
Dry run image 4

As we can observe, the current node 6 has its parent with a value of K. So, this node also satisfies the given condition.

  • 5th pass: Now, our current node is a leaf node with a value equal to K. So, this node also satisfies the given condition.
     

As we can observe our current node is a leaf node so both its left and right child will be NULL and hence will return true. As our current node also satisfies the condition true value will be returned from this leaf node.

Dry run image 5

For each binary tree node, first, we will check if the current node satisfies the given constraints in the problem statement or not. If it does, we will check for its left and right subtrees. If it does not, we will return false from that node only without checking for its left and right subtrees.

Must Read Recursive Binary Search.

Implementation in C++

#include <iostream>
#include <stddef.h>
using namespace std;

// Structure to represent a binary tree node
struct Node{
    int data;
    Node *left;
    Node *right;
    Node(int x){
        data = x;
        left = right = NULL;
    }
};

// Function to check if all nodes satisfy the given condition
bool pre_order(Node *root, Node *parent, int K){

    // Base condition
    if (root == NULL){
        return true;
    }

    // Check for the left child
    bool isLeftK = root->left != NULL && root->left->data == K;

    // Check for the right child
    bool isRightK = root->right != NULL && root->right->data == K;

    // Check for the parent
    bool isParentK = parent != NULL && parent->data == K;

    bool check = (isLeftK || isRightK || isParentK || root->data == K);

    // If current node doesn't satisfy the condition, return false
    if (!check){
        return false;
    }

    // Recur for left subtree
    check &= pre_order(root->left, root, K);

    // Recur for right subtree
    check &= pre_order(root->right, root, K);

    // Return the check at the end
    return check;
}

int main(){
    // Declaring the value of K
    int K = 5;

    // Creating the tree
    struct Node *root = new Node(5);
    root->left = new Node(7);
    root->right = new Node(6);
    root->right->right = new Node(5);

    //          5
    //         / \
    //        7   6
    //             \
    //              5

    // Call the pre_order function with flag as true, parent as NULL
    if (pre_order(root, NULL, K)){
        cout << "True" << endl;
    }
    else{
        cout << "False" << endl;
    }
    return 0;
}


Output:

Output image 1

Implementation in Java

public class MyClass{
    // Creating binary tree node
    static class node{
        int value;
        node right, left;
    };

    // Function to create a new node
    static node newnode(int key){
        node temp = new node();
        temp.value = key;
        temp.right = null;
        temp.left = null;

        return temp;
    }

    static boolean pre_order(node root, node parent, int K){

        // Base condition
        if (root == null){
            return true;
        }

        // Check for the left child
        boolean isLeftK = root.left != null && root.left.value == K;

        // Check for the right child
        boolean isRightK = root.right != null && root.right.value == K;

        // Check for the parent
        boolean isParentK = parent != null && parent.value == K;

        // Updating the check variable
        boolean check = (isLeftK || isRightK || isParentK || root.value == K);

        // If current node doesn't satisfy the condition, return false
        if (check == false){
            return false;
        }

        // Recur for left subtree
        check &= pre_order(root.left, root, K);

        // Recur for right subtree
        check &= pre_order(root.right, root, K);

        // Return the check at the end
        return check;
    }

    // Main code
    public static void main(String[] args){
        // Creating the tree
        node root = newnode(5);
        root.right = newnode(6);
        root.right.right = newnode(5);
        root.left = newnode(7);

        //          5
        //         / \
    	//        7   6
        //             \
    	//              5

        // Declaring the value of K
        int K = 5;

        // Function call to check binary tree
        boolean ans = pre_order(root, null, K);

        if (ans == false){
            System.out.print("False\n");
        }
        else{
            System.out.print("True\n");
        }
    }
}


Output:

Output image 2

Implementation in Python

# Function to create a binary tree Node
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.value = key

# Function to check if all nodes satisfy the given condition


def pre_order(root, parent, K):

    # Base condition
    if root == None:
        return True

    # Check for the left child
    isLeftK = root.left != None and root.left.value == K

    # Check for the right child
    isRightK = root.right != None and root.right.value == K

    # Check for the parent
    isParentK = parent != None and parent.value == K

    # Updating the check variable
    check = isLeftK or isRightK or isParentK or root.value == K

    # If current node doesn't satisfy the condition, return false
    if check == False:
        return False

    # Recur for left subtree
    check = check and pre_order(root.left, root, K)

    # Recur for right subtree
    check = check and pre_order(root.right, root, K)

    # Return the check at the end
    return check


# Main code
root = Node(5)
root.right = Node(6)
root.right.right = Node(5)
root.left = Node(7)

K = 5

# Calling function to check binary tree
ans = pre_order(root, None, K)

if ans == False:
    print("False")
else:
    print("True")


Output:

Output image 3

Time Complexity

O(N)

Explanation: The time required to traverse the binary tree in a preorder traversal is O(N) where N is the total number of nodes in the given binary tree.

Space Complexity

O(H)

Explanation: As we use recursion to traverse the tree, our space complexity becomes O(H). The recursion call stack will have a maximum of H elements at any time frame. The space complexity will be O(N) for a skewed binary tree where H refers to the height of the binary tree, and N refers to the total number of nodes in the given binary tree. However, if we ignore recursion, the space complexity of the approach discussed is O(1).

Must Read Binary Tree vs Binary Search Tree.

Frequently Asked Questions

What are the various different types of binary trees?

The different types of binary trees are full binary tee, complete binary tree, balanced binary tree, perfect binary tree and degenerate binary tree.

What are the applications of binary trees?

Binary Trees are used for implementing priority queues and performing encoding and decoding operations.

What is the difference between a leaf node and a root node?

In a binary tree, a leaf node is any node that does not possess any child node. In contrast, a root node is the first node on a binary tree, which all other nodes in the sequence stem from.

What are the various ways to navigate a binary tree?

In-order, pre-order, and post-order are the three typical ways to navigate through a binary tree in depth-first order.

What is a binary tree pre-order traversal?

One of the traversing methods used to visit the node in the tree is pre-order traversal. It adheres to the NLR principle (node-left-right). To determine a tree's prefix expression, pre-order traversal is employed.

What benefits and drawbacks do binary trees offer?

A binary tree's searching operation is quick, and they're also simple to use and comprehend. Many pointers in binary tree traversals are null and so worthless, and deletions in binary trees are difficult.

What is the difference between a binary tree and a binary search tree?

A binary search tree is a specific type of binary tree where the left child node has a value less than the parent node, and the right child node has a value greater than the parent node. This allows for efficient searching and insertion of elements in the tree.

Conclusion

In this blog, we discussed a problem based on binary trees and used the concept of the pre-order traversal in a Binary Tree to solve the problem. We learned to modify the pre-order traversal of the binary tree to check whether every node of the binary tree has a value K on itself or its immediate neighbors. It is usual to modify well-known algorithms to serve our purpose. We also saw the implementation of the solution approach in C++, Java and Python.

Recommended Reading:

Do check out The Interview guide for Product Based Companies, as well as some of the popular interview problems, asked in top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, and System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!

Previous article
Change a Binary Tree so that every node stores sum of all nodes in left subtree
Next article
Check if a Binary Tree Contains Duplicate Subtrees of Size 2 or More
Live masterclass