Generating all binary trees of N nodes in lexigraphical order

Question

I was just curious if anyone has an algorithm for how to generate binary trees of N nodes in lexigraphical order.

The very first binary tree would be a right chain of length N. The last tree would be a left chain of length N. I would like to know how to generate the trees in between the first binary tree and last binary tree in lexigraphical order.

A tree with 4 nodes would have 14 binary trees. A tree with 3 nodes would have 5 binary trees. etc.

EDIT: So, when you predorder traverse a tree, if you hit a non-null node you output a 1, if you hit a null output a 0. So the tree is ordered from 1,2,3,...N. A tree of node 5 would have a right chain of 1,2,3,4,5 in this order. I was thinking theoreticially this could work: If I just take the lowest numbered leaf node and reverse preorder traverse one position and move this node to that position. If this node was originally a child of its node-1, and after reverse preorder traversing this node is no longer a child of node-1, than I shift all LEAF nodes less than this node to the best possible preorder position (which should probably be the most right branch).

You haven't defined what lexicographical order means in this case. The concept usually applies to strings or sequences, not trees. — Matt Timmermans
So, when you predorder traverse a tree, if you hit a non-null node you output a 1, if you hit a null output a 0. So the tree is ordered from 1,2,3,...N. A tree of node 5 would have a right chain of 1,2,3,4,5 in this order. I was thinking theoreticially this could work: If I just take the lowest numbered leaf node and reverse preorder traverse one position and move this node to that position. If this node was originally a child of its node-1, and after reverse preorder traversing is no longer a child of node-1, than I shift all children leaf nodes less than the node to max predorder positions — jerrymail
The numbers 14 and 5 are a clue. They are the Catalan numbers for 4 and 3, respectively. — Reb.Cabin

6324 6324 · Accepted Answer · 2015-10-28T20:10:17

I won't give you a direct solution. But I will give an solution here for a similar problem: Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

I think it is not hard for you to modify my solution a little bit to solve your problem.

public class Solution {
    public List<TreeNode> generateTrees(int n) {
        return helper(1, n);
    }

    private List<TreeNode> helper(int start, int end) {
        List<TreeNode> result = new ArrayList<TreeNode>();

        if (start > end) {
            result.add(null);
            return result;
        }

        // You just need to understand how below for loop works.
        for (int i = start; i <= end; i++) {
            List<TreeNode> left = helper(start, i - 1);
            List<TreeNode> right = helper(i + 1, end);
            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    TreeNode root = new TreeNode(i);
                    root.left = l;
                    root.right = r;
                    result.add(root);
                }
            }
        }

        return result;
    }
}

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; left = null; right = null; }
}

The solution is pretty straightforward using Dynamic Programming.

Generating all binary trees of N nodes in lexigraphical order

1 Answers