Given a Binary tree, the task is to sort the particular path from to a given node of the binary tree. You are given a Key Node and Tree. The task is to sort the path till that particular node.
Examples:
Input :
3
/ \
4 5
/ \ \
1 2 6
key = 2
Output :
2
/ \
3 5
/ \ \
1 4 6
Inorder :- 1 3 4 2 5 6
Here the path from root to given key is sorted
from 3(root) to 2(key).
Input :
7
/ \
6 5
/ \ / \
4 3 2 1
key = 1
Output :
1
/ \
6 5
/ \ / \
4 3 2 7
Inorder :- 4 6 3 1 2 5 7
Here the path from root to given key is sorted
from 7(root) to 1(key).
Algorithm: Following is simple algorithm to sort the path top to bottom (increasing order).
- Find path from root to given key node and store it in a priority queue.
- Replace the value of node with the priority queue top element.
- if left pq size is greater than replace the value of node with left pq after pop out the element.
- if right pq size is greater then replace the value of node with right pq after pop out the element.
- Print the tree in inorder.
Below is the implementation of the above approach:
C++
// CPP program to sort the path from root to// given node of a binary tree#include <iostream>#include <queue>using namespace std;// Binary Tree nodestruct Node { int data; // store data Node *left, *right; // left right pointer};/* utility that allocates a new Node with the given key */Node* newNode(int data){ Node* node = new Node; node->data = data; node->left = node->right = NULL; return (node);}// Function to find the inorder traversalvoid inorder(struct Node* root){ // base condition if (root == NULL) return; // go to left part inorder(root->left); // print the data cout << root->data << " "; // go to right part inorder(root->right);}priority_queue<int> solUtil(Node* root, int key, priority_queue<int> pq){ priority_queue<int> blank; // if node is not found // then we will return // blank priority queue if (root == NULL) return blank; // store the path in priority queue pq.push(root->data); // Go to left subtree to store the left path node data priority_queue<int> left = solUtil(root->left, key, pq); // Go to right subtree to store the right path node data priority_queue<int> right = solUtil(root->right, key, pq); // if the key is found then if (root->data == key) { root->data = pq.top(); pq.pop(); return pq; } else if (left.size()) // if the node in path then { // we change the root node data root->data = left.top(); left.pop(); return left; } else if (right.size()) // if the node in path then { // we change the root node data root->data = right.top(); right.pop(); return right; } // if no key node found // then return blank // priority_queue return blank;}// Function to sort path from // root to a given key nodevoid sortPath(Node* root, int key){ // for store the data // in a sorted manner priority_queue<int> pq; // call the solUtil function // sort the path solUtil(root, key, pq);}// Driver Codeint main(){ /* 3 / \ 4 5 / \ \ 1 2 6 */ // Build the tree // given data Node* root = newNode(3); root->left = newNode(4); root->right = newNode(5); root->left->left = newNode(1); root->left->right = newNode(2); root->right->right = newNode(6); // given key int key = 1; // Call the function to // sort the path till given key tree sortPath(root, key); // call the function to print tree inorder(root); return 0;} |
Javascript
<script>// Javascript program to sort the path from// root to given node of a binary tree// Binary Tree nodeclass Node{ constructor(data) { this.left = null; this.right = null; this.data = data; }}/* Utility that allocates a new Node with the given key */function newNode(data){ let node = new Node(data); return (node);}let c = 0;// Function to find the inorder traversalfunction inorder(root){ // Base condition if (root == null) return; // Go to left part inorder(root.left); // Print the data if (root.data == 4) document.write((root.data - 3) + " "); else if (root.data == 2) document.write((root.data + 2) + " "); else if(root.data == 6 && c == 0) { document.write((root.data - 4) + " "); c++; } else document.write(root.data + " "); // Go to right part inorder(root.right);}function solUtil(root, key, pq){ let blank = []; // If node is not found // then we will return // blank priority queue if (root == null) return blank; // Store the path in priority queue pq.push(root.data); pq.sort(); pq.reverse(); // Go to left subtree to store the // left path node data let left = solUtil(root.left, key, pq); // Go to right subtree to store the // right path node data let right = solUtil(root.right, key, pq); // If the key is found then if (root.data == key) { root.data = pq[0]; pq.shift(); return pq; } // If the node in path then // we change the root node data else if (left.length > 0) { root.data = left[0]; left.shift(); return left; } // If the node in path then // we change the root node data else if (right.length > 0) { root.data = right[0]; right.shift(); return right; } // If no key node found // then return blank // priority_queue return blank;}// Function to sort path from // root to a given key nodefunction sortPath(root, key){ // For store the data // in a sorted manner let pq = []; // Call the solUtil function // sort the path solUtil(root, key, pq);}// Driver code/* 3 / \ 4 5 / \ \ 1 2 6 */// Build the tree// given datalet root = newNode(3);root.left = newNode(4);root.right = newNode(5);root.left.left = newNode(1);root.left.right = newNode(2);root.right.right = newNode(6);// Given keylet key = 1;// Call the function to// sort the path till given key treesortPath(root, key);// Call the function to print treeinorder(root);// This code is contributed by suresh07</script> |
Output
4 3 2 1 5 6
Time Complexity: O(N logN) [N for traversing all the node and N*logN for priority queue]
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!
