Reconstruct generic tree from booleans


  • 4
    S

    Generic tree, aka, n-ary tree: fanout degree has no restriction, i.e., any node may have 0 or 1 or 2 or more children, e.g:

    struct TreeNode {
      ValueType value;
      vector<TreeNode*> children;
    };
    

    Now you are given pre-order and post-order iterators that let you access nodes in the tree, and you want to build a new tree that has same structure as original tree.

    interface TreeIterator {
       public:
         bool hasNext();
         void next();
         ValueType getValue();
    
         bool isLeaf();  // Information you should use
    };
    

    class PreOrderTreeIterator implements TreeIterator {...}
    class PostOrderTreeIterator implements TreeIterator {...}

    Notice that, because of duplicates, you cannot rely on value to distinguish nodes. In other words, value is completely useless, the input is essentially two arrays of "isLeaf" booleans in pre-order and post-order traversal sequence.

    Can you still reconstruct the tree:

    TreeNode* reconstructTree(PreOrderTreeIterator preIter, PreOrderTreeIterator postIter) {
      // Implement this
    }

  • 0

    If the n-ary tree is a binary tree, according to this link, it's impossible to reconstruct a binary tree from its preorder and postorder outputs.

    As far as I know, we can reconstuct a binary tree from its preorder and postorder traversal if the tree is a full tree.

    I want to see if anybody knows how to solve this problem.


  • 0
    S

    Note the radical difference between this problem and other typical binary reconstruction problems: you are given information about whether node is leaf or not.

    Yes this problem is solvable. If input is valid, there will be one unique tree structure in output, you can also determine whether input is valid sequence, during the process of reconstructing tree.


  • 0

    Very interesting! Thanks a lot!


  • 0
    A
    public TreeNode compTreeNode(PreOrderTreeIterator preOrder, PostOrderTreeIterator postOrder) {
        return compTreeNode(preOrder, postOrder, null);
    }
    public TreeNode compTreeNode(PreOrderTreeIterator preOrder, PostOrderTreeIterator postOrder, TreeNode parent) {
          if(parent == null && preOrder.isLeaf()) {
               // invalid base case
               return null;
          }
          while(preOrder.hasNext()) {
              if(!preOrder.isLeaf()) {
                  if(parent == null) {
                       parent = new TreeNode(preOrder.getValue());
                       preOrder.next();
                       compTreeNode(preOrder, postOrder, parent);
                  } else {
                       TreeNode node = new TreeNode(preOrder.getValue());
                        parent.children.add(node);
                        preOrder.next();
                        return compTreeNode(preOrder, postOrder, node);
                  }
              } else {
                   while(preOrder.isLeaf() && postOrder.isLeaf()) {
                        TreeNode leaf = new TreeNode(preOrder.getValue());
                         parent.children.add(leaf);
                         preOrder.next();
                         postOrder.next();
                   }
                   return parent;
              }
          }
    }
    

  • 1
    C

    With recursion and comments, untested (curiously, there seems to be no need for hasNext()):

    // Precondition: pre points to some node r, post points to the first
    // node in the post-order traversal of the subtree rooted at r.
    //
    // Postcondition: post points to r, pre points to the last node in
    // the pre-order traversal of the subtree rooted at r.
    //
    // Returns the subtree rooted at r.
    TreeNode* reconstruct(PreOrderTreeIterator* pre, PreOrderTreeIterator* post) {
      TreeNode* r = new TreeNode{pre->getValue()};
      // Here, pre points to r.
      if (pre->isLeaf())
        return r; // r has no children, nothing to do.
      // r has at least one child.
      do {
        // post points to a leaf in some subtree below r.
        // First, we move pre to the root of this subtree.
        pre->next();
        // pre now points to the root of a child subtree of r, the same subtree where post points to a leaf.
        // So we can apply recursion to reconstruct this subtree.
        r->children.push_back(reconstructTree(pre, post));
        // Here, by the postcondition post points to the root of the subtree we just constructed.
        // We move post to the next node, which will either be a leaf in the next child subtree of r
        // or it will be r.
        post->next();
        // By checking whether we are at a leaf, we can distinguish between these two cases.
      } while (post->isLeaf());
      // post points to a non-leaf, which means it points to r, satisfying the postcondition.
      // We did not touch pre after the last recursive call, so pre still points to the last node
      // in the pre-order traversal of the last child subtree, which is the same as the last node
      // of the pre-order traversal of the tree rooted at r.
      return r;
    }
    
    TreeNode* reconstructTree(PreOrderTreeIterator preIter, PreOrderTreeIterator postIter) {
      return reconstruct(&preIter, &postIter);
    }
    

  • 0
    A

    My python solution that only builds the structure of the tree (not the values) for simplicity. The function takes numpy array of booleans as input (which can be built with the iterator) and outputs the root of the Tree.

    class Node:
        def __init__(self):
            self.children = []
    
    
    def find_subtree_length(pre_order, post_order):
        pre_leafs = 0
        pre_others = 0
        post_leafs = 0
        post_others = 0
        for i, a in enumerate(pre_order):
            pre_leafs += int(a)
            pre_others += int(not a)
            post_leafs += int(post_order[i])
            post_others += int(not post_order[i])
            if pre_leafs == post_leafs and pre_others == post_others:
                return i + 1
    
        raise Exception("Formating error")
    
    
    def build_tree(pre_order, post_order):
        root = Node()
        if len(pre_order) == 1:
            return root
    
        i = 1
        j = 0
        while i < len(pre_order):
            l = find_subtree_length(pre_order[i:], post_order[j:])
            child = build_tree(pre_order[i:i + l], post_order[j:j + l])
            root.children.append(child)
            i += l
            j += l
    
        return root
    
    

    And some simple test cases:

    
    import numpy as np
    
    
    def build_pre_order(node, values=None):
        if values is None:
            values = []
        values.append(len(node.children) == 0)
        for child in node.children:
            build_pre_order(child, values)
    
        # values.append("E")
        return values
    
    
    def build_post_order(node, values=None):
        if values is None:
            values = []
        for child in node.children:
            build_post_order(child, values)
    
        values.append(len(node.children) == 0)
        return values
    
    
    def test(pre, post):
        pre = np.array(pre)
        post = np.array(post)
        tree = build_tree(pre, post)
        assert np.array_equal(pre, build_pre_order(tree))
        assert np.array_equal(post, build_post_order(tree))
    
    
    test([False, True], [True, False])
    test([False, True, True, True], [True, True, True, False])
    test([False, True, False, True, True, True],
         [True, True, True, False, True, False])
    test([False, True, False, True, False, False, True, True, False, True, False, True, True],
         [True, True, False, True, False, True, False, True, True, False, True, False, False])
    
    

    I do not know if this is the simplest solution, but this seems to work.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.