Compress a Binary Tree from top to bottom with overlapping condition

0 0 10 minutes read

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
      \
       3
Output: 1 2
Explanation:
1 and 1 are at same vertical distance, count of set bit at 0^th position = 2 and count of clear bit = 0. Therefore, 0^th bit of the resultant node is set.
2 and 3 are at same vertical distance, count of set bit at 0^th 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 1^st pos = 2 and count of clear bit = 0. Therefore, 1st bit of resultant node is set.

Input:
       5
     /   \
    3     2
   / \   /  \
  1   4 1    2
Output: 1 3 5 2 2
Explanation:
5,4 and 1 are at same verticle distance (i.e 0), count of set bit at 0^th 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 1^st 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 2^nd 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     4
Output: 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 tree
class 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
//  line
void 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 distance
void 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 condition
void 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 Code
int 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 approach
import 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 tree
class 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 line
def 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 condition
def 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 Code
if __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 approach
using System;
using System.Collections.Generic;
 
// Structure of a node of the tree
class 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 tree
class 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 line
function 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 condition
function 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 Code
 
let 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 Call
compressTree(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 zambiatek!