Check whether every node of the binary tree has a value K on itself or its any immediate neighbours

Debarati Ghatak
Last Updated: May 13, 2022

Introduction

We are given a binary tree and an integer K as input in this question. We will have to check whether every given tree node has a value K on itself or any of its immediate neighbours and then return true or false.

The problem statement may seem to be very wordy, so let us break down the question into three smaller parts, and our task of finding the solution will become a lot easier. 

Our main task is to check whether each node in the tree,

  1. has value K
  2. has a parent with value K
  3. has children with value K


If any of the conditions are true for each tree node, our answer will be true. Otherwise, our answer will be false.

Problem Statement

Check whether every node of the binary tree has a value K on itself or its any immediate neighbours

Test Case

Let us take a few sample test cases to understand the question better.

Test Case 1

 

Input: K = 0

Output: True

As we can see, the above tree has three nodes: 0,1 and 1. 

Root node 0 is itself having value K. It’s left child, and right child, i.e. 1 and 1 are not having value k. But their parent, i.e. 0, has value K. This tree, therefore, satisfies the needed conditions.

So the answer is true.

Test Case 2

Input: K = 0

Output: False

In this given tree, if you observe, all the nodes satisfy the given conditions except node 4.

  • It is itself does not have value K
  • Its parent node does not have value K
  • None of its children has the value K. (Note that node 4 is a leaf node and does not have any children)


Test Case 3

 

Input: K = 1

Output: False

In this given tree, there is not even a single node with a K value of 1, so the answer is false.

Now that we understand the question entirely let us see how to approach it.

Source: Giphy

Approach

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

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

  1. If the node has value K
  2. If the parent of node has value K
  3. If any child of the node has value K
     

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

Steps of algorithm

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

C++ Code

#include <bits/stdc++.h>
using namespace std;
//Structure of Node
struct Node
{
	int data;
	Node *left;
	Node *right;
	Node(int x)
	{
		data = x;
		left = right = NULL;
	}
};
bool solve(bool flag, Node *root, Node *parent, int K)
{
	// Check the current node
	// If it is equal to K, recur for left and right subtrees
	// Else do the following
	if (root->data != K)
	{
		// Check if the left child is NULL or if left child has value K
		if (root->left == NULL or root->left->data != K)
		{
			// Check if the right child is NULL or if right child has value K
			if (root->right == NULL or root->right->data != K)
			{
				// Check if the parent is NULL or if the parent has value K
				if (parent == NULL or parent->data != K)
				{
					/* If the program reaches this line of code, it means that none of the three conditions is satisfied
					So return flag */
					flag = false;
					return flag;
				}
			}
		}	
	}
	// Recur for left subtree
	if (root->left)
	{
		// If the flag is true
		if (flag)
		{
			flag = solve(flag, root->left, root, K);
		}
	}
	// Recur for right subtree
	if (root->right)
	{
		// If the flag is true
		if (flag)
		{
			flag = solve(flag, root->right, root, K);
		}
	}
	// Return the flag at the end
	return flag;
}
int main()
{
	int K = 0;
	// Creating the tree
	struct Node *root = new Node(0);
	root->left = new Node(1);
	root->right = new Node(1);
//          0
//         / \
//        1   1
	// Call the solve function with flag as true, parent as NULL
	if (solve(true, root, NULL, K))
	cout << "True" << endl;
		else
	cout << "False" << endl;
	return 0;
}

Java Code

/* Java program */
import java.util.*;

class Main {

    /* Creating 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;
    }
    
     
    /* This function is to check binary
    tree whether its each node
    has value K or, it is connected
    with nodes with value K. */
    static boolean connectedK(node root,node parent,int K,boolean flag)
    {
        /* Checking node value */
        if (root.value != K)
        {
            /* Checking the left child value */
            if (root.left == null || root.left.value != K)
            {
                /* Checking the right child value */
                if (root.right == null || root.right.value != K)
                {
                    /* Checking the parent value */
                    if (parent == null || parent.value != K)
                    {
                        flag = false;
                        return flag;
                    }
                }
            }
        }
        
        /* Traversing to the left subtree */
        if (root.left != null)
        {
            if (flag == true)
            {
                flag = connectedK(root.left,
                root, K, flag);
            }
        }
        
        /* Traversing to the right subtree */
        if (root.right != null)
        {
            if (flag == true)
            {
                flag = connectedK(root.right,
                root, K, flag);
            }
        }
        return flag;
    }
    
    /* Main code */
    public static void main(String[] args)
    {
        node root = newnode(0);
        root.right = newnode(1);
        root.right.right = newnode(0);
        root.left = newnode(0);
        
        int K = 0;
        
        /* Function call to check binary tree */
        boolean result = connectedK(root, null, K, true);
        
        if (result == false)
            System.out.print("False\n");
        else
            System.out.print("True\n");
    }
}

Python Code

# Python3 program

class Node:
	def __init__(self,key):
		self.left = None
		self.right = None
		self.value = key
		
# This function is to check binary
# tree whether its each node
# has value K or, it is connected
# with node with value K.
def connectedK(root, parent, K, flag):
	
	# Checking node value
	if root.value != K:
		
		# Checking the left
		# child value
		if (root.left == None or
			root.left.value != K):
			
			# Checking the right
			# child value
			if (root.right == None or
				root.right.value != K):
				
				# Checking the parent value
				if (parent == None or
					parent.value != K):
					flag = False
					return flag
				
	# Traversing to the left subtree
	if root.left != None:
		if flag == True:
			flag = connectedK(root.left,
							root, K, flag)
	
	# Traversing to the right subtree
	if root.right != None:
		if flag == True:
			flag = connectedK(root.right,
							root, K, flag)
			
	return flag

# Main code
root = Node(0)
root.right = Node(1)
root.right.right = Node(0)
root.left = Node(0)

K = 0

# Calling function to check binary tree
result = connectedK(root, None, K, True)

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

Output

True

Complexity Analysis

Time Complexity: O(N)

O(N) time is taken to traverse the tree in a preorder fashion.

Here, N refers to the number of nodes in the given binary tree.

Space Complexity:  O(H)

As we use recursion to traverse the tree, our space complexity becomes O(H). The recursion call stack will have maximum O(H) elements at any time frame. The space complexity will be O(N) for a skewed binary tree. 

Here, H refers to height, and N refers to the number of nodes in the given binary tree. However, if we ignore recursion, the space complexity is O(1).

Frequently Asked Questions

Q1. What is a skewed binary tree?

Ans: A skewed binary tree is a special binary tree where each node has one child or no child. There can be two types of skewed binary trees:

  • Left-skewed binary tree
  • Right-skewed binary tree

For a left-skewed binary tree, all nodes either have left or no child. No node has a right child.

Similarly, all nodes have a right or no child for right-skewed binary trees.

Q2. Why is recursive tree traversal space complexity for a skewed binary tree O(N)? (N refers to the number of nodes in the given binary tree)

Ans: The space complexity of recursive tree traversal is always the height or depth of the tree. In the case of a skewed tree, the height is always equal to N or the total number of nodes. Therefore the space complexity becomes O(N).
 

Q3. What are the different types of binary trees?

Ans: The different types of binary trees are:

  • Full binary tree
  • Complete binary tree
  • Balanced binary tree
  • Perfect binary tree
  • Degenerate binary tree

You can learn more about the different binary trees from here.
 

Q4.  How to do preorder traversal of a binary tree iteratively without using recursion?

Ans: While recursion is the more popular way of traversing binary trees, we can also use iteration for traversal. 

The intuitive alternative to recursion is a stack data structure, and with stack, we can do preorder traversal of a given binary tree. Here is a little code snippet in C++ for you to understand how to use the stack for preorder traversal.
If you want to understand iterative preorder traversal in-depth, check out this awesome blog!
 

Q5. What is post-order traversal?
Ans: Post-order traversal is a traversal in which we travel to the left subtree of the node first, then to the right subtree, and then the node itself.

Key Takeaways

To conclude this blog, we learned how to approach and solve this question "Check whether every node of the binary tree has a value K on itself or its any immediate neighbors".

We solved the given question using preorder traversal while maintaining the two variables flag and parent at every step. You can use the same logic to solve this question using any other tree traversal of your choice.

If you want to learn more about Binary Trees, we have got you covered! Check out our amazing blogs on Binary Trees here.

Happy learning, Ninja!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think