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

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.

• 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.

• 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.

• 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.

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.

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;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

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");
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Output:

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")

You can also try this code with Online Python Compiler

Run Code

Output:

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:

• Create a Balanced Binary Tree using leaf Nodes of a Binary Tree without using Extra Space
• Check If all the Nodes in a Binary Tree Having Common Values are at least D Distance apart
• Construct a Binary Tree from a given Preorder and Inorder Traversal
• Construct a Complete Binary Tree from its Linked List Representation
• Diagonal Traversal of Binary Tree (Recursive and Iterative)
• Find the Minimum and Maximum Number of Nodes Between Critical Points
• Level Order Traversal in Spiral Form
• Application of Linked List
   

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!