Given a binary tree consisting of N nodes. Find the path between the node having the lowest value to the node having the highest value. There is no restriction on the traversal, i.e. the tree can be traversed upward, bottom, left and right.
Examples:
Input: N = 8
2
/ \
1 6
/ \ \
4 21 26
/ \
5 7{(2), (1, 6), (4, 21), (26), (5), (7)}
Output: 1 -> 2 -> 6 -> 26
Explanation: The minimum value in the tree is 1, while the maximum value is 26. So the path from the minimum value, i.e. 1 to the maximum value, i.e. 26 is 1 -> 2 -> 6 -> 26. Other than that, there is no other path from the node consisting of the minimum value to the node consisting of the maximum value.Input: N = 5
10
/ \
5 20
/ \
17 25{(10), (5, 20), (), (17, 25)}
Output: 5 -> 10 -> 20 -> 25
Explanation: The lowest node is 5 and the highest node is 25. The path between these two nodes is [5, 10, 20, 25].
Approach: This can be solved with the following idea:
- The first intuition that builds up in minds is to traverse the entire binary tree and find the node with the lowest and highest values.
- Then find the lowest common ancestor of the nodes with the lowest and highest values, then print the paths from the lowest node to the highest node using the parent pointers.
- We start at the highest value node and follow its parent pointers until we reach the lowest common ancestor. Then, we print the lowest common ancestor and follow the parent pointers of the lowest value node until we reach the next lowest common ancestor.
Below are the steps involved in the implementation of the code:
- The program below defines a TreeNode struct to represent a node in the binary tree.
- The findPath function takes the root node of the binary tree as input and finds the node with the lowest value and the node with the highest value by performing a breadth-first search of the tree.
- Then, the function traverses up from the lowest value node and the highest value node to find their common ancestor node.
- Finally, the function prints the path from the lowest value node to the common ancestor node and the path from the common ancestor node to the highest value node.
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// A structure to represent the node// of the treestruct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode* parent; TreeNode(int x) : val(x), left(NULL), right(NULL), parent(NULL) { }};// Function to find path between the node// having the lowest value to the node// having the highest value.void findPath(TreeNode* root){ TreeNode* minNode = root; TreeNode* maxNode = root; queue<TreeNode*> q; q.push(root); // Find the node with the lowest // value and the node with // the highest value while (!q.empty()) { TreeNode* node = q.front(); q.pop(); if (node->val < minNode->val) minNode = node; if (node->val > maxNode->val) maxNode = node; if (node->left) { node->left->parent = node; q.push(node->left); } if (node->right) { node->right->parent = node; q.push(node->right); } } // Traverse up from the lowest value // node until we reach the common // ancestor node while (minNode->parent != nullptr && minNode->parent->val > maxNode->val) { minNode = minNode->parent; } // Traverse up from the highest value // node until we reach the // common ancestor node while (maxNode->parent != nullptr && maxNode->parent->val < minNode->val) { maxNode = maxNode->parent; } // Print the path from the lowest // value node to the common // ancestor node cout << minNode->val << " "; // Print the path from the common // ancestor node to the // highest value node set<int> path; while (maxNode != nullptr) { path.insert(maxNode->val); maxNode = maxNode->parent; } for (auto itr = path.begin(); itr != path.end(); itr++) { cout << *itr << " "; } cout << endl;}// Driver codeint main(){ TreeNode* root = new TreeNode(2); root->left = new TreeNode(1); root->right = new TreeNode(6); root->left->left = new TreeNode(4); root->left->right = new TreeNode(21); root->right->right = new TreeNode(26); root->left->left->left = new TreeNode(5); root->left->right->right = new TreeNode(7); root->parent = NULL; // Function call findPath(root); return 0;} |
Java
// JAVA code for the above approach:import java.util.*;// A class to represent the node of the treeclass TreeNode { int val; TreeNode left; TreeNode right; TreeNode parent; TreeNode(int x) { val = x; left = null; right = null; parent = null; }}// Main classpublic class Main { // Function to find path between the node // having the lowest value to the node // having the highest value. public static void findPath(TreeNode root) { TreeNode minNode = root; TreeNode maxNode = root; Queue<TreeNode> q = new LinkedList<>(); q.add(root); // Find the node with the lowest // value and the node with // the highest value while (!q.isEmpty()) { TreeNode node = q.poll(); if (node.val < minNode.val) minNode = node; if (node.val > maxNode.val) maxNode = node; if (node.left != null) { node.left.parent = node; q.add(node.left); } if (node.right != null) { node.right.parent = node; q.add(node.right); } } // Traverse up from the lowest value // node until we reach the common // ancestor node while (minNode.parent != null && minNode.parent.val > maxNode.val) { minNode = minNode.parent; } // Traverse up from the highest value // node until we reach the // common ancestor node while (maxNode.parent != null && maxNode.parent.val < minNode.val) { maxNode = maxNode.parent; } // Print the path from the lowest // value node to the common // ancestor node System.out.print(minNode.val + " "); // Print the path from the common // ancestor node to the // highest value node Set<Integer> path = new TreeSet<>(); while (maxNode != null) { path.add(maxNode.val); maxNode = maxNode.parent; } for (int val : path) { System.out.print(val + " "); } System.out.println(); } // Driver code public static void main(String[] args) { TreeNode root = new TreeNode(2); root.left = new TreeNode(1); root.right = new TreeNode(6); root.left.left = new TreeNode(4); root.left.right = new TreeNode(21); root.right.right = new TreeNode(26); root.left.left.left = new TreeNode(5); root.left.right.right = new TreeNode(7); root.parent = null; // Function call findPath(root); }}// This code is contributed by rambabuguphka |
Python3
from queue import Queue# A class to represent the node of the treeclass TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None self.parent = None# Function to find the path between the node# having the lowest value to the node# having the highest value.def find_path(root): min_node = root max_node = root q = Queue() q.put(root) # Find the node with the lowest # value and the node with the # highest value while not q.empty(): node = q.get() if node.val < min_node.val: min_node = node if node.val > max_node.val: max_node = node if node.left: node.left.parent = node q.put(node.left) if node.right: node.right.parent = node q.put(node.right) # Traverse up from the lowest value # node until we reach the common # ancestor node while min_node.parent is not None and min_node.parent.val > max_node.val: min_node = min_node.parent # Traverse up from the highest value # node until we reach the # common ancestor node while max_node.parent is not None and max_node.parent.val < min_node.val: max_node = max_node.parent # Print the path from the lowest # value node to the common # ancestor node print(min_node.val, end=" ") # Print the path from the common # ancestor node to the # highest value node path = set() while max_node is not None: path.add(max_node.val) max_node = max_node.parent for val in sorted(path): print(val, end=" ") print()# Driver codeif __name__ == "__main__": # Create the binary tree root = TreeNode(2) root.left = TreeNode(1) root.right = TreeNode(6) root.left.left = TreeNode(4) root.left.right = TreeNode(21) root.right.right = TreeNode(26) root.left.left.left = TreeNode(5) root.left.right.right = TreeNode(7) root.parent = None # Function call to find and print the path find_path(root) |
C#
// C# code for the above approach:using System;using System.Collections.Generic;// A class to represent the node of the treepublic class TreeNode{ public int val; public TreeNode left; public TreeNode right; public TreeNode parent; public TreeNode(int x) { val = x; left = null; right = null; parent = null; }}// Main classpublic class GFG{ // Function to find path between the node // having the lowest value to the node // having the highest value. public static void FindPath(TreeNode root) { TreeNode minNode = root; TreeNode maxNode = root; Queue<TreeNode> q = new Queue<TreeNode>(); q.Enqueue(root); // Find the node with the lowest // value and the node with // the highest value while (q.Count > 0) { TreeNode node = q.Dequeue(); if (node.val < minNode.val) minNode = node; if (node.val > maxNode.val) maxNode = node; if (node.left != null) { node.left.parent = node; q.Enqueue(node.left); } if (node.right != null) { node.right.parent = node; q.Enqueue(node.right); } } // Traverse up from the lowest value // node until we reach the common // ancestor node while (minNode.parent != null && minNode.parent.val > maxNode.val) { minNode = minNode.parent; } // Traverse up from the highest value // node until we reach the // common ancestor node while (maxNode.parent != null && maxNode.parent.val < minNode.val) { maxNode = maxNode.parent; } // Print the path from the lowest // value node to the common // ancestor node Console.Write(minNode.val + " "); // Print the path from the common // ancestor node to the // highest value node SortedSet<int> path = new SortedSet<int>(); while (maxNode != null) { path.Add(maxNode.val); maxNode = maxNode.parent; } foreach (int val in path) { Console.Write(val + " "); } Console.WriteLine(); } // Driver code public static void Main(string[] args) { TreeNode root = new TreeNode(2); root.left = new TreeNode(1); root.right = new TreeNode(6); root.left.left = new TreeNode(4); root.left.right = new TreeNode(21); root.right.right = new TreeNode(26); root.left.left.left = new TreeNode(5); root.left.right.right = new TreeNode(7); root.parent = null; // Function call FindPath(root); }}// This code is contributed by Sakshi |
Javascript
<script> // Javascript code for the above approach: // A class to represent the node // of the tree class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; this.parent = null; } } // Function to find path between the node // having the lowest value to the node // having the highest value. function findPath(root) { let minNode = root; let maxNode = root; const queue = []; queue.push(root); // Find the node with the lowest // value and the node with // the highest value while (queue.length !== 0) { const node = queue.shift(); if (node.val < minNode.val) minNode = node; if (node.val > maxNode.val) maxNode = node; if (node.left) { node.left.parent = node; queue.push(node.left); } if (node.right) { node.right.parent = node; queue.push(node.right); } } // Traverse up from the lowest value // node until we reach the common // ancestor node while (minNode.parent !== null && minNode.parent.val > maxNode.val) { minNode = minNode.parent; } // Traverse up from the highest value // node until we reach the // common ancestor node while (maxNode.parent !== null && maxNode.parent.val < minNode.val) { maxNode = maxNode.parent; } // Print the path from the lowest // value node to the // highest value node let path = []; while (maxNode !== null) { path.push(maxNode.val); maxNode = maxNode.parent; } document.write(minNode.val + " " + path.reverse().join(" ")); } // Driver code function main() { const root = new TreeNode(2); root.left = new TreeNode(1); root.right = new TreeNode(6); root.left.left = new TreeNode(4); root.left.right = new TreeNode(21); root.right.right = new TreeNode(26); root.left.left.left = new TreeNode(5); root.left.right.right = new TreeNode(7); root.parent = null; // Function call findPath(root); } main(); // This code is contributed by Pushpesh Raj </script> |
Output
1 2 6 26
Time Complexity: O(N)
Auxiliary Space: O(h)
