Search code examples
algorithmbinary-tree

Unique binary search trees, leetcode terminology

I'm looking at the leetcode question that asks to enumerate all unique binary search trees (https://leetcode.com/problems/unique-binary-search-trees-ii/). They encode each tree as an array. However, I can't figure out how to get from the trees to the arrays. For n=3 we get the trees:

enter image description here

And the corresponding arrays:

[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Completely lost as to how they intend the trees be mapped to the corresponding arrays. In the first tree for example, they start at 1. But then, they go all the way down to the leaf, 2 and reach 3 last.

Solution

  • I guess the order of the array is different to the order of the trees.

    Number the trees from 0 to 4 from left to right, the trees represented by the array should be: [1, 0, 2, 4, 3]

    I am not entirely sure how this is done for trees with bigger depth, but I guess this might unambiguous, since it is a search tree. So following one node value are the values of the left and right child node or null if there is none. All trailing nulls are omitted. Does this make sense?