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 preorder, inorder, and postorder. A Binary tree is a widely asked data structure in programming contests and technical interviews.

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

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,

If the current node has a value equal to K.

If the parent of the current node has a value equal to K.

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

Start preorder traversal of the tree with check = True, parent = NULL.

Check whether the current node has value K. If not, check the following.

Check if the left child is NULL or has the value K.

Check if the right child is NULL or has the value K.

Check if the parent is NULL or has the value K.

Recur for the left subtree.

Recur for the right subtree.

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.

#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:

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:

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:

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

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.