Number of turns to reach from one node to other in binary tree
Given a binary tree and two nodes. The task is to count the number of turns needed to reach from one node to another node of the Binary tree.
Examples:
Input: Below Binary Tree and two nodes 5 & 6 1 / \ 2 3 / \ / \ 4 5 6 7 / / \ 8 9 10 Output: Number of Turns needed to reach from 5 to 6: 3 Input: For above tree if two nodes are 1 & 4 Output: Straight line : 0 turn
Idea based on the Lowest Common Ancestor in a Binary Tree
We have to follow the step.
- Find the LCA of given two nodes
- Given node present either on the left side or right side or equal to LCA.
- According to the above condition, our program falls under one of the two cases
Case 1: If none of the nodes is equal to LCA, we get these nodes either on the left side or right side. We call two functions for each node. ....a) if (CountTurn(LCA->right, first, false, &Count) || CountTurn(LCA->left, first, true, &Count)) ; ....b) Same for second node. ....Here Count is used to store number of turns needed to reach the target node. Case 2: If one of the nodes is equal to LCA_Node, then we count only the number of turns needed to reached the second node. If LCA == (Either first or second) ....a) if (countTurn(LCA->right, second/first, false, &Count) || countTurn(LCA->left, second/first, true, &Count)) ;
3… Working of CountTurn Function
// we pass turn true if we move
// left subtree and false if we
// move right subTree
CountTurn(LCA, Target_node, count, Turn) // if found the key value in tree if (root->key == key) return true; case 1: If Turn is true that means we are in left_subtree If we going left_subtree then there is no need to increment count else Increment count and set turn as false case 2: if Turn is false that means we are in right_subtree if we going right_subtree then there is no need to increment count else increment count and set turn as true. // if key is not found. return false;
Below is the implementation of the above idea.
C++
Java
Python3
C#
Javascript
Output
4
Time Complexity: O(n)
Alternate Solution:
We have to follow the step:
- Find the LCA of the given two nodes
- Store the path of two-node from LCA in strings S1 and S2 that will store ‘l’ if we have to take a left turn in the path starting from LCA to that node and ‘r’ if we take a right turn in the path starting from LCA.
- Reverse one of the strings and concatenate both strings.
- Count the number of time characters in our resultant string not equal to its adjacent character.
Implementation:
C++
// C++ Program to count number of turns // in a Binary Tree. #include <bits/stdc++.h> using namespace std; // A Binary Tree Node struct Node { struct Node* left, *right; int key; }; // Utility function to create a new // tree Node Node* newNode( int key) { Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return temp; } //Preorder traversal to store l or r in the string traversing //from LCA to the given node key void findPath( struct Node* root, int d,string str,string &s){ if (root==NULL){ return ; } if (root->key==d){ s=str; return ; } findPath(root->left,d,str+ "l" ,s); findPath(root->right,d,str+ "r" ,s); } // Utility function to find the LCA of // two given values n1 and n2. struct Node* findLCAUtil( struct Node* root, int n1, int n2, bool &v1, bool &v2){ // Base case if (root == NULL) return NULL; if (root->key == n1){ v1= true ; return root; } if (root->key == n2){ v2= true ; return root; } // Look for keys in left and right subtrees Node* left_lca = findLCAUtil(root->left, n1, n2,v1,v2); Node* right_lca = findLCAUtil(root->right, n1, n2,v1,v2); if (left_lca && right_lca){ return root; } return (left_lca != NULL) ? left_lca : right_lca; } bool find(Node* root, int x){ if (root==NULL){ return false ; } if ((root->key==x) || find(root->left,x) || find(root->right,x)){ return true ; } return false ; } //Function should return LCA of two nodes if both nodes are //present otherwise should return NULL Node* findLCA( struct Node* root, int first, int second){ bool v1= false ; bool v2= false ; Node* lca = findLCAUtil(root,first,second,v1,v2); if ((v1&&v2) || (v1&&find(lca,second)) || (v2&&find(lca,first))){ return lca; } return NULL; } // function should return the number of turns required to go from //first node to second node int NumberOFTurns( struct Node* root, int first, int second){ // base cases if root is not present or both node values are same if (root==NULL || (first==second)){ return 0; } string s1 = "" ; string s2 = "" ; Node* lca = findLCA(root,first,second); findPath(lca,first, "" ,s1); findPath(lca,second, "" ,s2); if (s1.length()==0 && s2.length()==0){ return -1; } reverse(s1.begin(),s1.end()); s1+=s2; int cnt=0; bool flag= false ; for ( int i=0; i<(s1.length()-1); i++){ if (s1[i]!=s1[i+1]){ flag= true ; cnt+=1; } } if (!flag){ return -1; } return cnt; } // Driver program to test above functions int main() { // Let us create binary tree given in the above // example Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->right->right = newNode(7); root->left->left->left = newNode(8); root->right->left->left = newNode(9); root->right->left->right = newNode(10); int turn = 0; if ((turn = NumberOFTurns(root, 5, 10))!=-1) cout << turn << endl; else cout << "Not Possible" << endl; return 0; } |
Java
// Java code for the above approach import java.util.Stack; // A Binary Tree Node class Node { Node left, right; int key; Node( int key) { this .key = key; left = right = null ; } } class BinaryTree { // Utility function to create a new tree Node static Node newNode( int key) { Node temp = new Node(key); return temp; } // Preorder traversal to store l or r in the string // traversing from LCA to the given node key static void findPath(Node root, int d, String str, StringBuilder s) { if (root == null ) { return ; } if (root.key == d) { s.append(str); return ; } findPath(root.left, d, str + "l" , s); findPath(root.right, d, str + "r" , s); } // Utility function to find the LCA of two given values // n1 and n2. static Node findLCAUtil(Node root, int n1, int n2) { // Base case if (root == null ) return null ; if (root.key == n1) return root; if (root.key == n2) return root; // Look for keys in left and right subtrees Node left_lca = findLCAUtil(root.left, n1, n2); Node right_lca = findLCAUtil(root.right, n1, n2); if (left_lca != null && right_lca != null ) { return root; } return (left_lca != null ) ? left_lca : right_lca; } // Function should return LCA of two nodes if both nodes // are present otherwise should return null static Node findLCA(Node root, int first, int second) { if (root == null ) { return null ; } Node lca = findLCAUtil(root, first, second); // if both nodes are present in the tree if (find(lca, first) && find(lca, second)) { return lca; } return null ; } static boolean find(Node root, int x) { if (root == null ) { return false ; } if ((root.key == x) || find(root.left, x) || find(root.right, x)) { return true ; } return false ; } // function should return the number of turns required // to go from // first node to second node static int numberOfTurns(Node root, int first, int second) { // base cases if root is not present or both node // values are same if (root == null || (first == second)) { return 0 ; } StringBuilder s1 = new StringBuilder(); StringBuilder s2 = new StringBuilder(); Node lca = findLCA(root, first, second); findPath(lca, first, "" , s1); findPath(lca, second, "" , s2); if (s1.length() == 0 && s2.length() == 0 ) { return - 1 ; } s1.reverse(); s1.append(s2); int cnt = 0 ; boolean flag = false ; for ( int i = 0 ; i < (s1.length() - 1 ); i++) { if (s1.charAt(i) != s1.charAt(i + 1 )) { flag = true ; cnt += 1 ; } } if (!flag) { return - 1 ; } return cnt; } // Driver program to test above functions public static void main(String[] args) { // Let us create binary tree given in the above // example Node root = newNode( 1 ); root.left = newNode( 2 ); root.right = newNode( 3 ); root.left.left = newNode( 4 ); root.left.right = newNode( 5 ); root.right.left = newNode( 6 ); root.right.right = newNode( 7 ); root.left.left.left = newNode( 8 ); root.right.left.left = newNode( 9 ); root.right.left.right = newNode( 10 ); System.out.println(numberOfTurns(root, 5 , 10 )); } } // This code is contributed by Potta Lokesh |
Python3
# Python Program to count number of turns # in a Binary Tree. # A Binary Tree Node class Node: def __init__( self , key): self .key = key self .left = None self .right = None # Utility function to find the LCA of # two given values n1 and n2. def findLCAUtil(root, n1, n2, v1, v2): # Base case if root is None : return None if root.key = = n1: v1[ 0 ] = True return root if root.key = = n2: v2[ 0 ] = True return root # Look for keys in left and right subtrees left_lca = findLCAUtil(root.left, n1, n2, v1, v2) right_lca = findLCAUtil(root.right, n1, n2, v1, v2) if left_lca and right_lca: return root return left_lca if left_lca is not None else right_lca # Function should return LCA of two nodes if both nodes are # present otherwise should return None def findLCA(root, first, second): v1 = [ False ] v2 = [ False ] lca = findLCAUtil(root, first, second, v1, v2) if v1[ 0 ] and v2[ 0 ] or (v1[ 0 ] and find(root, second)) or (v2[ 0 ] and find(root, first)): return lca return None # Utility function to create a new # tree Node def newNode(key): temp = Node(key) temp.left = None temp.right = None return temp # function to find path from LCA to the given node key def findPath(root, d, string, s): if root is None : return if root.key = = d: s[ 0 ] = string return findPath(root.left, d, string + "l" , s) findPath(root.right, d, string + "r" , s) def find(root, x): if root is None : return False if root.key = = x or find(root.left, x) or find(root.right, x): return True return False # function should return the number of turns required to go from # first node to second node def NumberOFTurns(root, first, second): # base cases if root is not present or both node values are same if root is None or first = = second: return 0 s1 = [""] s2 = [""] lca = findLCA(root, first, second) findPath(lca, first, "", s1) findPath(lca, second, "", s2) if len (s1[ 0 ]) = = 0 and len (s2[ 0 ]) = = 0 : return - 1 s1[ 0 ] = s1[ 0 ][:: - 1 ] + s2[ 0 ] cnt = 0 flag = False for i in range ( len (s1[ 0 ]) - 1 ): if s1[ 0 ][i] ! = s1[ 0 ][i + 1 ]: flag = True cnt + = 1 if not flag: return - 1 return cnt # Create binary tree root = newNode( 1 ) root.left = newNode( 2 ) root.right = newNode( 3 ) root.left.left = newNode( 4 ) root.left.right = newNode( 5 ) root.right.left = newNode( 6 ) root.right.right = newNode( 7 ) root.left.left.left = newNode( 8 ) root.right.left.left = newNode( 9 ) root.right.left.right = newNode( 10 ) # Find number of turns between two nodes turn = 0 turn = NumberOFTurns(root, 5 , 10 ) if turn ! = - 1 : print (turn) else : print ( "Not Possible" ) |
Javascript
// A Binary Tree Node class Node { constructor(key) { this .key = key; this .left = null ; this .right = null ; } } // Utility function to create a new tree Node function newNode(key) { const temp = new Node(key); return temp; } // Preorder traversal to store l or r in the string traversing from LCA to the given node key function findPath(root, d, str, s) { if (root === null ) return ; if (root.key === d) { s.value = str; return ; } findPath(root.left, d, str + "l" , s); findPath(root.right, d, str + "r" , s); } // Utility function to find the LCA of two given values n1 and n2. function findLCAUtil(root, n1, n2, v1, v2) { // Base case if (root === null ) return null ; if (root.key === n1) { v1.value = true ; return root; } if (root.key === n2) { v2.value = true ; return root; } // Look for keys in left and right subtrees const left_lca = findLCAUtil(root.left, n1, n2, v1, v2); const right_lca = findLCAUtil(root.right, n1, n2, v1, v2); if (left_lca && right_lca) return root; return left_lca !== null ? left_lca : right_lca; } function find(root, x) { if (root === null ) return false ; if (root.key === x || find(root.left, x) || find(root.right, x)) return true ; return false ; } // Function should return LCA of two nodes if both nodes are present otherwise should return NULL function findLCA(root, first, second) { const v1 = { value: false }; const v2 = { value: false }; const lca = findLCAUtil(root, first, second, v1, v2); if ((v1.value && v2.value) || (v1.value && find(lca, second)) || (v2.value && find(lca, first))) return lca; return null ; } // Function should return the number of turns required to go from first node to second node function NumberOFTurns(root, first, second) { // Base cases if root is not present or both node values are the same if (root === null || first === second) return 0; const s1 = { value: "" }; const s2 = { value: "" }; const lca = findLCA(root, first, second); findPath(lca, first, "" , s1); findPath(lca, second, "" , s2); if (s1.value.length === 0 && s2.value.length === 0) return -1; s1.value = s1.value.split( "" ).reverse().join( "" ); s1.value += s2.value; let cnt = 0; let flag = false ; for (let i = 0; i < s1.value.length - 1; i++) { if (s1.value[i] !== s1.value[i + 1]) { flag = true ; cnt += 1; } } if (!flag) return -1; return cnt; } // Let us create binary tree given in the above // example let root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.left.left.left = newNode(8); root.right.left.left = newNode(9); root.right.left.right = newNode(10); let turn = 0; if ((turn = NumberOFTurns(root, 5, 10))!=-1) console.log(turn); else console.log( "Not Possible" ); |
C#
// C# Program to count number of turns // in a Binary Tree. using System; using System.Linq; // A Binary Tree Node public class Node { public Node left, right; public int key; } public class Program { // Utility function to create a new // tree Node public static Node newNode( int key) { Node temp = new Node(); temp.key = key; temp.left = temp.right = null ; return temp; } // Preorder traversal to store l or r in the string // traversing from LCA to the given node key public static void findPath(Node root, int d, string str, ref string s) { if (root == null ) { return ; } if (root.key == d) { s = str; return ; } findPath(root.left, d, str + "l" , ref s); findPath(root.right, d, str + "r" , ref s); } // Utility function to find the LCA of // two given values n1 and n2. public static Node findLCAUtil(Node root, int n1, int n2, ref bool v1, ref bool v2) { if (root == null ) { return null ; } if (root.key == n1) { v1 = true ; return root; } if (root.key == n2) { v2 = true ; return root; } // Look for keys in left and right subtrees Node left_lca = findLCAUtil(root.left, n1, n2, ref v1, ref v2); Node right_lca = findLCAUtil(root.right, n1, n2, ref v1, ref v2); if (left_lca != null && right_lca != null ) { return root; } return (left_lca != null ) ? left_lca : right_lca; } public static bool find(Node root, int x) { if (root == null ) { return false ; } if ((root.key == x) || find(root.left, x) || find(root.right, x)) { return true ; } return false ; } // Function should return LCA of two nodes if both nodes // are present otherwise should return NULL public static Node findLCA(Node root, int first, int second) { bool v1 = false ; bool v2 = false ; Node lca = findLCAUtil(root, first, second, ref v1, ref v2); if ((v1 && v2) || (v1 && find(lca, second)) || (v2 && find(lca, first))) { return lca; } return null ; } // function should return the number of turns required // to go from // first node to second node public static int NumberOFTurns(Node root, int first, int second) { // base cases if root is not present or both node // values are same if (root == null || (first == second)) { return 0; } string s1 = "" ; string s2 = "" ; Node lca = findLCA(root, first, second); findPath(lca, first, "" , ref s1); findPath(lca, second, "" , ref s2); if (s1.Length == 0 && s2.Length == 0) { return -1; } s1 = new string (s1.Reverse().ToArray()); s1 += s2; int cnt = 0; bool flag = false ; for ( int i = 0; i < s1.Length - 1; i++) { if (s1[i] != s1[i + 1]) { flag = true ; cnt += 1; } } if (!flag) { return -1; } return cnt; } // Driver program to test above functions static void Main( string [] args) { // Let us create binary tree given in the above // example Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.left.left.left = newNode(8); root.right.left.left = newNode(9); root.right.left.right = newNode(10); int turn = 0; if ((turn = NumberOFTurns(root, 5, 10)) != -1) { Console.WriteLine(turn); } else { Console.WriteLine( "Not Possible" ); } } } |
Output
4
Time Complexity: O(n)
Contact Us