Given a binary tree and a node in the binary tree, find Levelorder Predecessor of the given node. That is, the node that appears before the given node in the level order traversal of the tree.
Note: The task is not just to print the data of the node, you have to return the complete node from the tree.
Examples:
Consider the following binary tree
20
/ \
10 26
/ \ / \
4 18 24 27
/ \
14 19
/ \
13 15
Levelorder traversal of given tree is:
20, 10, 26, 4, 18, 24, 27, 14, 19, 13, 15
Input : 19
Output : 14
Input : 4
Output : 26
Approach:
- Check if the root is NULL, that is tree is empty. If true then return NULL.
- Check if the given node is root. If true then there will be no predecessor of root, so return NULL.
- Otherwise, perform Level Order Traversal on the tree using a Queue and a temporary pointer prev to maintain the last node during the traversal.
- At every step of the level order traversal, check if the current node matches with the given node.
- If True, stop traversing any further and return the node stored in the pointer prev as it is the node accessed just before the current node during the traversal.
Below is the implementation of the above approach:
C++
// CPP program to find Levelorder// Predecessor of given node in the// Binary Tree#include <bits/stdc++.h>using namespace std;// Tree Nodestruct Node { struct Node *left, *right; int value;};// Utility function to create a// new node with given valuestruct Node* newNode(int value){ Node* temp = new Node; temp->left = temp->right = NULL; temp->value = value; return temp;}// Function to find the Level Order Predecessor// of a given Node in Binary TreeNode* levelOrderPredecessor(Node* root, Node* key){ // Base Case if (root == NULL) return NULL; // If root equals to key if (root == key) { // There is no Predecessor of // root node return NULL; } // Create an empty queue for level // order traversal queue<Node*> q; // Enqueue Root q.push(root); // Temporary node to keep track of the // last node Node* prev = NULL; while (!q.empty()) { Node* nd = q.front(); q.pop(); if (nd == key) break; else prev = nd; if (nd->left != NULL) { q.push(nd->left); } if (nd->right != NULL) { q.push(nd->right); } } return prev;}// Driver codeint main(){ struct Node* root = newNode(20); root->left = newNode(10); root->left->left = newNode(4); root->left->right = newNode(18); root->right = newNode(26); root->right->left = newNode(24); root->right->right = newNode(27); root->left->right->left = newNode(14); root->left->right->left->left = newNode(13); root->left->right->left->right = newNode(15); root->left->right->right = newNode(19); struct Node* key = root->left->right->right; struct Node* res = levelOrderPredecessor(root, key); if (res) cout << "LevelOrder Predecessor of " << key->value << " is " << res->value; else cout << "LevelOrder Predecessor of " << key->value << " is " << "NULL"; return 0;} |
Java
// Java program to find Levelorder // Predecessor of given node in the // Binary Tree import java.util.*;class GfG { // Tree Node static class Node { Node left, right; int value; } // Utility function to create a // new node with given value static Node newNode(int value) { Node temp = new Node(); temp.left = null; temp.right = null; temp.value = value; return temp; } // Function to find the Level Order Predecessor // of a given Node in Binary Tree static Node levelOrderPredecessor(Node root, Node key) { // Base Case if (root == null) return null; // If root equals to key if (root == key) { // There is no Predecessor of // root node return null; } // Create an empty queue for level // order traversal Queue<Node> q = new LinkedList<Node> (); // Enqueue Root q.add(root); // Temporary node to keep track of the // last node Node prev = null; while (!q.isEmpty()) { Node nd = q.peek(); q.remove(); if (nd == key) break; else prev = nd; if (nd.left != null) { q.add(nd.left); } if (nd.right != null) { q.add(nd.right); } } return prev; } // Driver code public static void main(String[] args) { Node root = newNode(20); root.left = newNode(10); root.left.left = newNode(4); root.left.right = newNode(18); root.right = newNode(26); root.right.left = newNode(24); root.right.right = newNode(27); root.left.right.left = newNode(14); root.left.right.left.left = newNode(13); root.left.right.left.right = newNode(15); root.left.right.right = newNode(19); Node key = root.left.right.right; Node res = levelOrderPredecessor(root, key); if (res != null) System.out.println("LevelOrder Predecessor of " + key.value + " is " + res.value); else System.out.println("LevelOrder Predecessor of " + key.value+ " is null"); }} |
Python3
"""Python3 program to find Level order Predecessor of given node in the Binary Tree"""# A Binary Tree Node # Utility function to create a # new tree node class newNode: # Constructor to create a newNode def __init__(self, data): self.value = data self.left = None self.right = self.parent = None# Function to find the Level Order Predecessor # of a given Node in Binary Tree def levelOrderPredecessor(root, key) : # Base Case if (root == None) : return None # If root equals to key if (root == key): # There is no Predecessor of # root node return None # Create an empty queue for level # order traversal q = [] # Enqueue Root q.append(root) # Temporary node to keep track # of the last node prev = None while (len(q)): nd = q[0] q.pop(0) if (nd == key) : break else: prev = nd if (nd.left != None): q.append(nd.left) if (nd.right != None): q.append(nd.right) return prev# Driver Codeif __name__ == '__main__': root = newNode(20) root.left = newNode(10) root.left.left = newNode(4) root.left.right = newNode(18) root.right = newNode(26) root.right.left = newNode(24) root.right.right = newNode(27) root.left.right.left = newNode(14) root.left.right.left.left = newNode(13) root.left.right.left.right = newNode(15) root.left.right.right = newNode(19) key = root.left.right.right res = levelOrderPredecessor(root, key) if (res) : print("LevelOrder Predecessor of", key.value, "is", res.value) else: print("LevelOrder Predecessor of", key.value, "is", "None")# This code is contributed by# SHUBHAMSINGH10 |
C#
// C# program to find Levelorder // Predecessor of given node in the // Binary Treeusing System;using System.Collections.Generic;class GfG{ // Tree Node class Node { public Node left, right; public int value; } // Utility function to create a // new node with given value static Node newNode(int value) { Node temp = new Node(); temp.left = null; temp.right = null; temp.value = value; return temp; } // Function to find the Level Order Predecessor // of a given Node in Binary Tree static Node levelOrderPredecessor(Node root, Node key) { // Base Case if (root == null) return null; // If root equals to key if (root == key) { // There is no Predecessor of // root node return null; } // Create an empty queue for level // order traversal Queue<Node> q = new Queue<Node> (); // Enqueue Root q.Enqueue(root); // Temporary node to keep track of the // last node Node prev = null; while (q.Count!=0) { Node nd = q.Peek(); q.Dequeue(); if (nd == key) break; else prev = nd; if (nd.left != null) { q.Enqueue(nd.left); } if (nd.right != null) { q.Enqueue(nd.right); } } return prev; } // Driver code public static void Main(String[] args) { Node root = newNode(20); root.left = newNode(10); root.left.left = newNode(4); root.left.right = newNode(18); root.right = newNode(26); root.right.left = newNode(24); root.right.right = newNode(27); root.left.right.left = newNode(14); root.left.right.left.left = newNode(13); root.left.right.left.right = newNode(15); root.left.right.right = newNode(19); Node key = root.left.right.right; Node res = levelOrderPredecessor(root, key); if (res != null) Console.WriteLine("LevelOrder Predecessor of " + key.value + " is " + res.value); else Console.WriteLine("LevelOrder Predecessor of " + key.value+ " is null"); }} // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript program to find Levelorder // Predecessor of given node in the // Binary Tree // Tree Node class Node { constructor(value) { this.left = null; this.right = null; this.value = value; } } // Utility function to create a // new node with given value function newNode(value) { let temp = new Node(value); return temp; } // Function to find the Level Order Predecessor // of a given Node in Binary Tree function levelOrderPredecessor(root, key) { // Base Case if (root == null) return null; // If root equals to key if (root == key) { // There is no Predecessor of // root node return null; } // Create an empty queue for level // order traversal let q = []; // Enqueue Root q.push(root); // Temporary node to keep track of the // last node let prev = null; while (q.length > 0) { let nd = q[0]; q.shift(); if (nd == key) break; else prev = nd; if (nd.left != null) { q.push(nd.left); } if (nd.right != null) { q.push(nd.right); } } return prev; } let root = newNode(20); root.left = newNode(10); root.left.left = newNode(4); root.left.right = newNode(18); root.right = newNode(26); root.right.left = newNode(24); root.right.right = newNode(27); root.left.right.left = newNode(14); root.left.right.left.left = newNode(13); root.left.right.left.right = newNode(15); root.left.right.right = newNode(19); let key = root.left.right.right; let res = levelOrderPredecessor(root, key); if (res != null) document.write("LevelOrder Predecessor of " + key.value + " is " + res.value); else document.write("LevelOrder Predecessor of " + key.value+ " is null"); </script> |
Output
LevelOrder Predecessor of 19 is 14
Complexity Analysis:
- Time Complexity: O(N), as we are using a while loop which will traverse N times, where N is the number of nodes in the tree.
- Auxiliary Space: O(N), as we are using extra space for the queue, which we are using for the level order traversal.
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!
