Given a binary tree consisting of distinct values and two numbers K1 and K2, the task is to find all nodes that lie between them in the inorder sequence of the tree.
Examples:
Input:
1
/ \
12 11
/ / \
3 4 13
\ /
15 9
k1 = 12
k2 = 15
Output:
1 4
Explanation:
Inorder sequence is 3 12 1 4 15 11 9 13
The common nodes between 12 and 15 in the inorder sequence of the tree are {1, 4}.
Input:
5
/ \
21 77
/ \ \
61 16 36
\ /
10 3
/
23
k1 = 23
k2 = 3
Output:
10 5 77
Explanation:
Inorder sequence is 61 21 16 23 10 5 77 3 36
The common nodes between 23 and 3 in the inorder sequence of the tree are {10, 5, 77}.
Approach:
In order to solve this problem, we are using the Morris Inorder Traversal of a Binary Tree to avoid the use of any extra space. We are keeping a flag to set when either of K1 or K2 is found. Once found, print every node that appears in the inorder sequence until the other node is found.
Below is the implementation of the above approach:
C++
// C++ Program to find// the common nodes// between given two nodes// in the inorder sequence// of the binary tree#include <bits/stdc++.h>using namespace std;// Definition of Binary// Tree Structurestruct tNode { int data; struct tNode* left; struct tNode* right;};// Helper function to allocate// memory to create new nodesstruct tNode* newtNode(int data){ struct tNode* node = new tNode; node->data = data; node->left = NULL; node->right = NULL; return (node);}// Flag to set if// either of K1 or// K2 is foundint flag = 0;// Function to traverse the// binary tree without recursion// and without stack using// Morris Traversalvoid findCommonNodes(struct tNode* root, int K1, int K2){ struct tNode *current, *pre; if (root == NULL) return; current = root; while (current != NULL) { if (current->left == NULL) { if (current->data == K1 || current->data == K2) { if (flag) { return; } else { flag = 1; } } else if (flag) { cout << current->data << " "; } current = current->right; } else { // Find the inorder predecessor // of current pre = current->left; while (pre->right != NULL && pre->right != current) pre = pre->right; // Make current as the right // child of its inorder // predecessor if (pre->right == NULL) { pre->right = current; current = current->left; } // Revert the changes made // to restore the original tree // i.e., fix the right child // of predecessor else { pre->right = NULL; if (current->data == K1 || current->data == K2) { if (flag) { return; } else { flag = 1; } } else if (flag) { cout << current->data << " "; } current = current->right; } // End of if condition pre->right == NULL } // End of if condition current->left == NULL } // End of while}// Driver codeint main(){ struct tNode* root = newtNode(1); root->left = newtNode(12); root->right = newtNode(11); root->left->left = newtNode(3); root->right->left = newtNode(4); root->right->right = newtNode(13); root->right->left->right = newtNode(15); root->right->right->left = newtNode(9); int K1 = 12, K2 = 15; findCommonNodes(root, K1, K2); return 0;} |
Java
// Java program to find the common nodes// between given two nodes in the inorder // sequence of the binary treeimport java.util.*;class GFG{// Definition of Binary Tree static class tNode { int data; tNode left; tNode right;};// Helper function to allocate// memory to create new nodesstatic tNode newtNode(int data){ tNode node = new tNode(); node.data = data; node.left = null; node.right = null; return (node);}// Flag to set if either // of K1 or K2 is foundstatic int flag = 0;// Function to traverse the binary // tree without recursion and // without stack using // Morris Traversalstatic void findCommonNodes(tNode root, int K1, int K2){ tNode current, pre; if (root == null) return; current = root; while (current != null) { if (current.left == null) { if (current.data == K1 || current.data == K2) { if (flag == 1) { return; } else { flag = 1; } } else if (flag == 1) { System.out.print(current.data + " "); } current = current.right; } else { // Find the inorder predecessor // of current pre = current.left; while (pre.right != null && pre.right != current) { pre = pre.right; } // Make current as the right // child of its inorder // predecessor if (pre.right == null) { pre.right = current; current = current.left; } // Revert the changes made // to restore the original tree // i.e., fix the right child // of predecessor else { pre.right = null; if (current.data == K1 || current.data == K2) { if (flag == 1) { return; } else { flag = 1; } } else if (flag == 1) { System.out.print(current.data + " "); } current = current.right; } // End of if condition pre.right == null } // End of if condition current.left == null } // End of while}// Driver codepublic static void main(String[] args){ tNode root = newtNode(1); root.left = newtNode(12); root.right = newtNode(11); root.left.left = newtNode(3); root.right.left = newtNode(4); root.right.right = newtNode(13); root.right.left.right = newtNode(15); root.right.right.left = newtNode(9); int K1 = 12, K2 = 15; findCommonNodes(root, K1, K2);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the # above approachfrom collections import deque# A Tree nodeclass Node: def __init__(self, x): self.data = x self.left = None self.right = None# Flag to set if# either of K1 or# K2 is foundflag = 0# Function to traverse the# binary tree without recursion# and without stack using# Morris Traversaldef findCommonNodes(root, K1, K2): global flag current, pre = None, None if (root == None): return current = root while (current != None): if (current.left == None): if (current.data == K1 or current.data == K2): if (flag): return else: flag = 1 elif (flag): print(current.data, end = " ") else: None current = current.right else: # Find the inorder # predecessor of current pre = current.left while (pre.right != None and pre.right != current): pre = pre.right # Make current as the right # child of its inorder # predecessor if (pre.right == None): pre.right = current current = current.left # Revert the changes made # to restore the original tree # i.e., fix the right child # of predecessor else: pre.right = None if (current.data == K1 or current.data == K2): if (flag): return else: flag = 1 elif (flag): print(current.data, end = " ") current = current.right # End of if condition # pre.right == None # End of if condition #current.left == None # End of while# Driver codeif __name__ == '__main__': root = Node(1) root.left = Node(12) root.right = Node(11) root.left.left = Node(3) root.right.left = Node(4) root.right.right = Node(13) root.right.left.right = Node(15) root.right.right.left = Node(9) K1 = 12 K2 = 15 findCommonNodes(root, K1, K2)# This code is contributed by Mohit Kumar 29 |
C#
// C# program to find the common nodes// between given two nodes in the inorder // sequence of the binary treeusing System;class GFG{// Definition of Binary Tree class tNode { public int data; public tNode left; public tNode right;};// Helper function to allocate// memory to create new nodesstatic tNode newtNode(int data){ tNode node = new tNode(); node.data = data; node.left = null; node.right = null; return (node);}// Flag to set if either // of K1 or K2 is foundstatic int flag = 0;// Function to traverse the binary // tree without recursion and // without stack using // Morris Traversalstatic void findCommonNodes(tNode root, int K1, int K2){ tNode current, pre; if (root == null) return; current = root; while (current != null) { if (current.left == null) { if (current.data == K1 || current.data == K2) { if (flag == 1) { return; } else { flag = 1; } } else if (flag == 1) { Console.Write(current.data + " "); } current = current.right; } else { // Find the inorder predecessor // of current pre = current.left; while (pre.right != null && pre.right != current) { pre = pre.right; } // Make current as the right // child of its inorder // predecessor if (pre.right == null) { pre.right = current; current = current.left; } // Revert the changes made // to restore the original tree // i.e., fix the right child // of predecessor else { pre.right = null; if (current.data == K1 || current.data == K2) { if (flag == 1) { return; } else { flag = 1; } } else if (flag == 1) { Console.Write(current.data + " "); } current = current.right; } // End of if condition pre.right == null } // End of if condition current.left == null } // End of while}// Driver codepublic static void Main(String[] args){ tNode root = newtNode(1); root.left = newtNode(12); root.right = newtNode(11); root.left.left = newtNode(3); root.right.left = newtNode(4); root.right.right = newtNode(13); root.right.left.right = newtNode(15); root.right.right.left = newtNode(9); int K1 = 12, K2 = 15; findCommonNodes(root, K1, K2);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program to find the common nodes// between given two nodes in the inorder// sequence of the binary tree// Definition of Binary Treeclass Node{ // Helper function to allocate// memory to create new nodes constructor(data) { this.data = data; this.left = this.right=null; } }// Flag to set if either// of K1 or K2 is foundlet flag = 0;// Function to traverse the binary// tree without recursion and// without stack using// Morris Traversalfunction findCommonNodes(root, K1, K2){ let current, pre; if (root == null) return; current = root; while (current != null) { if (current.left == null) { if (current.data == K1 || current.data == K2) { if (flag == 1) { return; } else { flag = 1; } } else if (flag == 1) { document.write(current.data + " "); } current = current.right; } else { // Find the inorder predecessor // of current pre = current.left; while (pre.right != null && pre.right != current) { pre = pre.right; } // Make current as the right // child of its inorder // predecessor if (pre.right == null) { pre.right = current; current = current.left; } // Revert the changes made // to restore the original tree // i.e., fix the right child // of predecessor else { pre.right = null; if (current.data == K1 || current.data == K2) { if (flag == 1) { return; } else { flag = 1; } } else if (flag == 1) { document.write(current.data + " "); } current = current.right; } // End of if condition pre.right == null } // End of if condition current.left == null } // End of while}// Driver codelet root = new Node(1);root.left = new Node(12);root.right = new Node(11);root.left.left = new Node(3);root.right.left = new Node(4);root.right.right = new Node(13);root.right.left.right = new Node(15);root.right.right.left = new Node(9);let K1 = 12, K2 = 15;findCommonNodes(root, K1, K2);// This code is contributed by patel2127</script> |
Output:
1 4
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
