Given a binary tree, the task is to compress all the nodes on the same vertical line into a single node such that if the count of set bits of all the nodes on a vertical line at any position is greater than the count of clear bits at that position, then the bit of the single node at that position is set.
Examples:
Input:
1 \ 2 / 1 \ 3Output: 1 2
Explanation:
1 and 1 are at same vertical distance, count of set bit at 0th position = 2 and count of clear bit = 0. Therefore, 0th bit of the resultant node is set.
2 and 3 are at same vertical distance, count of set bit at 0th pos = 1 and count of clear bit = 1. Therefore, 0 bit is set of resultant node is not set.
2 and 3 are at same vertical distance, count of set bit at 1st pos = 2 and count of clear bit = 0. Therefore, 1st bit of resultant node is set.
Input:
5 / \ 3 2 / \ / \ 1 4 1 2Output: 1 3 5 2 2
Explanation:
5,4 and 1 are at same verticle distance (i.e 0), count of set bit at 0th position = 2 and count of clear bit = 1. Therefore, 1th bit of the resultant node is set.
5,4 and 1 are at same verticle distance (i.e 0), count of set bit at 1st position = 0 and count of clear bit = 3. Therefore, 0th bit of the resultant node is set.
5,4 and 1 are at same verticle distance (i.e 0), count of set bit at 2nd position = 2 and count of clear bit = 1. Therefore, 1th bit of the resultant node is set.
Rest of the nodes are at distinct verticle distance.Input:
1 / \ 2 3 / \ / \ 11 3 4 10 / / \ \ \ 9 7 8 2 4Output: 9 11 2 1 2 10 4
Approach: The idea is to traverse the tree and to keep the track of the horizontal distance from the root node for each visited node. Below are the steps:
- A map can be used to store the horizontal distance from the root node as the key and the values of the nodes as values.
- After storing the values in the map check the number of set and non-set bits for each position and calculate the values accordingly.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Structure of a node of the treeclass Node {public: int val; Node *left, *right; Node(int val) { this->val = val; left = right = NULL; }};// Function to compress all the nodes on the same vertical// linevoid evalComp(vector<int>& arr){ // Stores node by compressing all nodes on the current // vertical line int ans = 0; // Check if i-th bit of current bit set or not int getBit = 1; // Iterate over the range [0, 31] for (int i = 0; i < 32; i++) { // Stores count of set bits at i-th positions int S = 0; // Stores count of clear bits at i-th positions int NS = 0; // Traverse the array for (auto j : arr) { // If i-th bit of current element is set if (getBit & j) S++; // Update S else NS++; // Update NS } // If count of set bits at i-th position is greater // than count of clear bits if (S > NS) // Update ans ans += pow(2, i); // Update getBit getBit <<= 1; } cout << ans << " ";}// Function to traverse the tree and map all the nodes of// same vertical line to vertical distancevoid Trav(Node* root, int hd, map<int, vector<int> >& mp){ if (!root) return; // Storing the values in the map mp[hd].push_back(root->val); // Recursive calls on left and right subtree Trav(root->left, hd - 1, mp); Trav(root->right, hd + 1, mp);}// Function to compress all the nodes on the same vertical// line with a single node that satisfies the conditionvoid compressTree(Node* root){ // Map all the nodes on the same vertical line map<int, vector<int> > mp; Trav(root, 0, mp); // Getting the range of horizontal distances int lower, upper; for (auto i : mp) { lower = min(lower, i.first); upper = max(upper, i.first); } for (int i = lower; i <= upper; i++) evalComp(mp[i]);}// Driver Codeint main(){ Node* root = new Node(5); root->left = new Node(3); root->right = new Node(2); root->left->left = new Node(1); root->left->right = new Node(4); root->right->left = new Node(1); root->right->right = new Node(2); // Function Call compressTree(root); return 0;}// This code is contributed by Tapesh(tapeshdua420) |
Java
// Java program for the above approachimport java.util.*;class GFG { // Structure of a node of the tree static class Node { int val; Node left, right; Node(int val) { this.val = val; left = right = null; } } // Driver Code public static void main(String[] args) { Node root = new Node(5); root.left = new Node(3); root.right = new Node(2); root.left.left = new Node(1); root.left.right = new Node(4); root.right.left = new Node(1); root.right.right = new Node(2); compressTree(root); } // Function to compress all the nodes on the same // vertical line public static void evalComp(ArrayList<Integer> arr) { // Stores node by compressing all nodes on the // currentvertical line int ans = 0; // Check if i-th bit of current bit set or not int getBit = 1; // Iterate over the range [0, 31] for (int i = 0; i < 32; i++) { // Stores count of set bits at i-th positions int S = 0; // Stores count of clear bits at i-th positions int NS = 0; // Traverse the array for (int j : arr) { // If i-th bit of current element is set if ((getBit & j) != 0) S++; // Update S else NS++; // Update NS } // If count of set bits at i-th position is // greater // than count of clear bits if (S > NS) // Update ans ans += Math.pow(2, i); // Update getBit getBit <<= 1; } System.out.print(ans + " "); } // Function to traverse the tree and map all the nodes // of same vertical line to vertical distance public static void Trav(Node root, int hd, HashMap<Integer, ArrayList<Integer> > mp) { if (root == null) return; // Storing the values in the map mp.putIfAbsent(hd, new ArrayList<>()); mp.get(hd).add(root.val); // Recursive calls on left and right subtree Trav(root.left, hd - 1, mp); Trav(root.right, hd + 1, mp); } // Function to compress all the nodes on the same // vertical // line with a single node that satisfies the condition public static void compressTree(Node root) { // Map all the nodes on the same vertical line HashMap<Integer, ArrayList<Integer> > mp = new HashMap<>(); Trav(root, 0, mp); // Getting the range of horizontal distances int lower = Integer.MAX_VALUE, upper = Integer.MIN_VALUE; for (Map.Entry<Integer, ArrayList<Integer> > i : mp.entrySet()) { lower = Math.min(lower, i.getKey()); upper = Math.max(upper, i.getKey()); } for (int i = lower; i <= upper; i++) evalComp(mp.get(i)); }}// This code is contributed by Tapesh(tapeshdua420) |
Python3
# Python3 program for the above approach# Structure of a node# of the treeclass TreeNode: def __init__(self, val ='', left = None, right = None): self.val = val self.left = left self.right = right # Function to compress all the nodes # on the same vertical linedef evalComp(arr): # Stores node by compressing all # nodes on the current vertical line ans = 0 # Check if i-th bit of current bit # set or not getBit = 1 # Iterate over the range [0, 31] for i in range(32): # Stores count of set bits # at i-th positions S = 0 # Stores count of clear bits # at i-th positions NS = 0 # Traverse the array for j in arr: # If i-th bit of current element # is set if getBit & j: # Update S S += 1 else: # Update NS NS += 1 # If count of set bits at i-th position # is greater than count of clear bits if S > NS: # Update ans ans += 2**i # Update getBit getBit <<= 1 print(ans, end = " ")# Function to compress all the nodes on# the same vertical line with a single node # that satisfies the conditiondef compressTree(root): # Map all the nodes on the same vertical line mp = {} # Function to traverse the tree and map # all the nodes of same vertical line # to vertical distance def Trav(root, hd): if not root: return # Storing the values in the map if hd not in mp: mp[hd] = [root.val] else: mp[hd].append(root.val) # Recursive calls on left and right subtree Trav(root.left, hd-1) Trav(root.right, hd + 1) Trav(root, 0) # Getting the range of # horizontal distances lower = min(mp.keys()) upper = max(mp.keys()) for i in range(lower, upper + 1): evalComp(mp[i])# Driver Codeif __name__ == '__main__': root = TreeNode(5) root.left = TreeNode(3) root.right = TreeNode(2) root.left.left = TreeNode(1) root.left.right = TreeNode(4) root.right.left = TreeNode(1) root.right.right = TreeNode(2) # Function Call compressTree(root) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;// Structure of a node of the treeclass Node { public int val; public Node left; public Node right; public Node(int data) { val = data; left = right = null; }}class Program { // Driver Code static void Main(string[] args) { Node root = new Node(5); root.left = new Node(3); root.right = new Node(2); root.left.left = new Node(1); root.left.right = new Node(4); root.right.left = new Node(1); root.right.right = new Node(2); compressTree(root); } // Function to compress all the nodes on the same // vertical line public static void evalComp(List<int> arr) { // Stores node by compressing all nodes on the // currentvertical line int ans = 0; // Check if i-th bit of current bit set or not int getBit = 1; // Iterate over the range [0, 31] for (int i = 0; i < 32; i++) { // Stores count of set bits at i-th positions int S = 0; // Stores count of clear bits at i-th positions int NS = 0; // Traverse the array foreach(int j in arr) { // If i-th bit of current element is set if ((getBit & j) != 0) S++; // Update S else NS++; // Update NS } // If count of set bits at i-th position is // greater // than count of clear bits if (S > NS) // Update ans ans += (int)Math.Pow(2, i); // Update getBit getBit <<= 1; } Console.Write(ans + " "); } // Function to traverse the tree and map all the nodes // of same vertical line to vertical distance public static void Trav(Node root, int hd, Dictionary<int, List<int> > mp) { if (root == null) return; // Storing the values in the map if (mp.ContainsKey(hd) == false) mp[hd] = new List<int>(); mp[hd].Add(root.val); // Recursive calls on left and right subtree Trav(root.left, hd - 1, mp); Trav(root.right, hd + 1, mp); } // Function to compress all the nodes on the same // vertical // line with a single node that satisfies the condition public static void compressTree(Node root) { // Map all the nodes on the same vertical line Dictionary<int, List<int> > mp = new Dictionary<int, List<int> >(); Trav(root, 0, mp); // Getting the range of horizontal distances int lower = Int32.MaxValue, upper = Int32.MinValue; foreach(KeyValuePair<int, List<int> > i in mp) { lower = Math.Min(lower, i.Key); upper = Math.Max(upper, i.Key); } for (int i = lower; i <= upper; i++) evalComp(mp[i]); }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
<script>// Javascript program for the above approach// Structure of a node// of the treeclass TreeNode { constructor(val = "", left = null, right = null) { this.val = val; this.left = left; this.right = right; }}// Function to compress all the nodes// on the same vertical linefunction evalComp(arr) { // Stores node by compressing all // nodes on the current vertical line let ans = 0; // Check if i-th bit of current bit // set or not let getBit = 1; // Iterate over the range [0, 31] for (let i = 0; i < 32; i++) { // Stores count of set bits // at i-th positions let S = 0; // Stores count of clear bits // at i-th positions let NS = 0; // Traverse the array for (j of arr) { // If i-th bit of current element // is set if (getBit & j) // Update S S += 1; // Update NS else NS += 1; } // If count of set bits at i-th position // is greater than count of clear bits if (S > NS) // Update ans ans += 2 ** i; // Update getBit getBit <<= 1; } document.write(ans + " ");}// Function to compress all the nodes on// the same vertical line with a single node// that satisfies the conditionfunction compressTree(root) { // Map all the nodes on the same vertical line let mp = new Map(); // Function to traverse the tree and map // all the nodes of same vertical line // to vertical distance function Trav(root, hd) { if (!root) return; // Storing the values in the map if (!mp.has(hd)) mp.set(hd, [root.val]); else { let temp = mp.get(hd); temp.push(root.val); mp.set(hd, temp); } // Recursive calls on left and right subtree Trav(root.left, hd - 1); Trav(root.right, hd + 1); } Trav(root, 0); // Getting the range of // horizontal distances let lower = [...mp.keys()].sort((a, b) => a - b)[0]; let upper = [...mp.keys()].sort((a, b) => b - a)[0]; for (let i = lower; i <= upper; i++) evalComp(mp.get(i));}// Driver Codelet root = new TreeNode(5);root.left = new TreeNode(3);root.right = new TreeNode(2);root.left.left = new TreeNode(1);root.left.right = new TreeNode(4);root.right.left = new TreeNode(1);root.right.right = new TreeNode(2);// Function CallcompressTree(root);// This code is contributed by _saurabh_jaiswal.</script> |
Output:
1 3 5 2 2
Time Complexity: O(N logN), where N is the number of nodes in the binary tree.
Auxiliary Space: O(N)
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!
