Being Code Expert: Tree

Showing posts with label Tree. Show all posts

How to construct tree from preorder and inorder

Given pre-order and in-order traversals of a binary tree, write a function to reconstruct the tree.

For example, given the following preorder traversal:

[a, b, d, e, c, f, g]

And the following inorder traversal:

[d, b, e, a, f, c, g]

You should return the following tree:

    a
   / \
  b   c
 / \ / \
d  e f  g

Example:

Input: preorder = {'a', 'b', 'd', 'e', 'c', 'f', 'g'}, inorder = {'d', 'b', 'e', 'a', 'f', 'c', 'g'}
Output: [a,b,c,d,e,f,g]

Approach

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode

struct TreeNode
{
    char data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(char data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

int prestart;
TreeNode *buildTree(vector<char> &preorder, 
      vector<char> &inorder,
                    int instart, int inend)
{
    if (instart > inend)
        return NULL;
    TreeNode *root = new TreeNode(preorder[prestart++]);
    if (instart == inend)
        return root;
    int k = 0;
    for (int i = instart; i <= inend; i++)
    {
        if (inorder[i] == root->data)
        {
            k = i;
            break;
        }
    }

    root->left = buildTree(preorder, inorder, instart, k - 1);
    root->right = buildTree(preorder, inorder, k + 1, inend);
    return root;
}
TreeNode *buildTree(vector<char> &preorder, 
     vector<char> &inorder)
{
    prestart = 0;
    if (preorder.size() == 0)
        return NULL;
    return buildTree(preorder, inorder, 0, inorder.size() - 1);
}

void printTree(TreeNode *root)
{
    queue<TreeNode *> q;
    q.push(root);
    vector<string> vec;
    while (!q.empty())
    {
        root = q.front();
        q.pop();
        if (root == NULL)
            vec.push_back("null");
        else
            vec.push_back(string(1, root->data));
        if (root != NULL)
        {
            q.push(root->left);
            q.push(root->right);
        }
    }
    int j = vec.size() - 1;
    while (j > 0 && vec[j] == "null")
        j--;
    vec.resize(j);
    cout << "[";
    for (int i = 0; i < j; i++)
        cout << vec[i] << ",";
    cout << vec[j];

    cout << "]";
}
int main()
{
    vector<char> preorder = {'a', 'b', 'd', 'e', 'c', 'f', 'g'};
    vector<char> inorder = {'d', 'b', 'e', 'a', 'f', 'c', 'g'};
    TreeNode *root = buildTree(preorder, inorder);
    printTree(root);
    return 0;
}

Recover a Tree From Preorder Traversal

We run a preorder depth-first search (DFS) on the root of a binary tree.

At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node. If the depth of a node is D, the depth of its immediate child is D + 1. The depth of the root node is 0.

If a node has only one child, that child is guaranteed to be the left child.

Given the output traversal of this traversal, recover the tree and return its root.

Example 1:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

Example 2:

Input: traversal = "1-2--3---4-5--6---7"
Output: [1,2,5,3,null,6,null,4,null,7]

Example 3:

Input: traversal = "1-401--349---90--88"
Output: [1,401,null,349,88,90]

Approach

C++

#include <bits/stdc++.h>
using namespace std;

//struct for treenode
struct TreeNode
{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

int pos;
TreeNode *recoverTree(string &traversal, int level)
{
    //if we reach end of the string
    //then return NULL
    if (traversal[pos] == '\0')
        return NULL;
    int curr = 0;

    //count depth of the next node
    while (traversal[pos + curr] == '-')
        curr++;

    //if depth of node is same as level
    if (curr == level)
    {
        pos += curr;
        int val = 0;

        //get the value at the current node
        while (traversal[pos] >= '0' && traversal[pos] <= '9')
        {
            val = (val * 10) + traversal[pos] - '0';
            pos++;
        }

        //create a new node with that value
        TreeNode *root = new TreeNode(val);

        //call for left by increasing a level
        root->left = recoverTree(traversal, level + 1);

        //call for right by increasing a level
        root->right = recoverTree(traversal, level + 1);

        //return the root of the tree
        return root;
    }

    //return null
    return NULL;
}
TreeNode *recoverFromPreorder(string traversal)
{

    pos = 0;
    return recoverTree(traversal, 0);
}
void printTree(TreeNode *root)
{
    queue<TreeNode *> q;
    q.push(root);
    vector<string> vec;
    while (!q.empty())
    {
        root = q.front();
        q.pop();
        if (root == NULL)
            vec.push_back("null");
        else
            vec.push_back(to_string(root->data));
        if (root != NULL)
        {
            q.push(root->left);
            q.push(root->right);
        }
    }
    int j = vec.size() - 1;
    while (j > 0 && vec[j] == "null")
        j--;
    vec.resize(j);
    cout << "[";
    for (int i = 0; i < j; i++)
        cout << vec[i] << ",";
    cout << vec[j];
    cout << "]";
}
int main()
{
    string traversal = "1-2--3--4-5--6--7";

    TreeNode *root = recoverFromPreorder(traversal);

    printTree(root);

    return 0;
}

Separating Numbers

We are given a tree with $N$ nodes. Each node has a color $C_{i}$ . We are also given $N - 1$ queries and in each query we are told to destroy a previously undestroyed edge. Every time we destroy an edge, we have to report the number of pairs of nodes that get disconnected. Here, two nodes $i$ and $j$ are said to be disconnected if before the destruction you could reach from $i$ to $j$ using edges not yet destroyed , and if $C_{i} = C_{j}$ .

Constraint:

$N \leq 300, 000$

$C [i] \leq 100, 000$

Example:

Input:
5
5 4
2 5
3 2
1 2
5 1 5 4 5
2 1 3 4
Output:
2
0
1
0

Approach

Java

import java.util.Map;
import java.util.TreeMap;

public class SeparatingNumbers {
    private static int C = 312345;
    private static long[] ans = new long[C];

    public static void main(String[] args) {
        int N = 5;

        int ar2D[][] = { { 5, 4 }, { 2, 5 }, { 3, 2 }, { 1, 2 } };
        int[] u = new int[C];
        int[] v = new int[C];
        for (int i = 0; i < N - 1; i++) {
            u[i] = ar2D[i][0] - 1;
            v[i] = ar2D[i][1] - 1;
        }
        int[] c = { 5, 1, 5, 4, 5 };
        // in order -1
        int[] order = { 1, 0, 2, 3 };
        DisjointSetUnion dsu = new DisjointSetUnion(N, c);
        for (int i = N - 2; i >= 0; i--) {
            int x = u[order[i]];
            int y = v[order[i]];
            ans[i] = dsu.merge(x, y);
        }
        for (int i = 0; i < N - 1; i++) {
            System.out.println(ans[i]);
        }
    }

    static public class DisjointSetUnion {

        private int rank[], parent[], size[];
        private TreeMap<Integer, Integer> map[];
        private int n;

        public DisjointSetUnion(int n, int c[]) {
            this.n = n;
            makeSet(c);
        }

        private void makeSet(int c[]) {
            rank = new int[n];
            parent = new int[n];
            map = new TreeMap[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
                map[i] = new TreeMap<>();
                increment(map[i], c[i], 1);
            }
        }

        public int find(int x) {
            if (parent[x] != x)
                parent[x] = find(parent[x]);
            return parent[x];
        }

        public long merge(int x, int y) {
            int xRoot = find(x);
            int yRoot = find(y);

            if (xRoot == yRoot)
                return getCount(map[xRoot], map[xRoot]);

            size[xRoot] = size[yRoot] = size[xRoot] + size[yRoot];

            long count = getCount(map[xRoot], map[yRoot]);

            if (rank[xRoot] < rank[yRoot]) {
                parent[xRoot] = yRoot;
                merge(map[yRoot], map[xRoot]);
            } else {
                parent[yRoot] = xRoot;
                merge(map[xRoot], map[yRoot]);
                if (rank[xRoot] == rank[yRoot]) {
                    rank[xRoot]++;
                }
            }

            return count;
        }

        // into x
        private void merge(TreeMap<Integer, Integer> x, TreeMap<Integer, Integer> y) {
            for (Map.Entry<Integer, Integer> entry : y.entrySet()) {
                increment(x, entry.getKey(), entry.getValue());
            }
        }

        private long getCount(TreeMap<Integer, Integer> x, TreeMap<Integer, Integer> y) {
            if (x.size() > y.size()) {
                return getCount(y, x);
            }
            long ans = 0;
            for (Map.Entry<Integer, Integer> entry : x.entrySet()) {
                ans += (long) entry.getValue() * get(y, entry.getKey());
            }
            return ans;
        }
    }

    static void increment(TreeMap<Integer, Integer> map, int key, int x) {
        Integer value = map.get(key);
        if (value == null) {
            map.put(key, x);
        } else {
            map.put(key, value + x);
        }
    }

    static int get(TreeMap<Integer, Integer> map, int key) {
        Integer value = map.get(key);
        if (value == null) {
            return 0;
        }
        return value;
    }

}

Home

How to construct tree from preorder and inorder

Recover a Tree From Preorder Traversal

Separating Numbers