I do leetcoding every once a while, but keep forgetting some tree basics. This post here it to help with that.
Types of Tree
Trees can have multiple children. Or on the special case of binary trees have only two. A binary tree is still different from a binary search tree (BST) where things follow a certain order.
Binary search tree
For a Binary tree to be a BST, it has to follow the following rules:
 left node must be smaller than parent.
 right node must be greater than parent.
Basically left < parent < right
Order of insertion matters for BST
Example 1
Let’s say you have the following numbers [1,2,3,4]
in your tree. Depending on the order you add them into the binary search tree, the tree’s visualization would be different.
A: Inserting in the following order: [4,3,2,1]
will create:
4
/
3
/
2
/
1
B: Inserting in the following order: [4,2,3,1]
or [4,2,1,3]
will create:
4
/
2
/ \
1 3
C: Inserting in the following order: [2,1,3,4]
or [2,3,1,4]
will create:
2
/ \
1 3
\
4
D: Inserting in the following order: [3,4,1,2]
or [3,1,4,2]
will create:
3
/ \
1 4
\
2
E: Inserting [1,2,3,4]
will create
1
\
2
\
3
\
4
and so on.
All the above are a BST made of 1,2,3,4. Because all conform to the two rules. Yet each is inserted with different order.
Tree Traversal
 Breadth First Search (BFS). Also known as levelorder traversal.
 Depth First Search (DFS).
Binary Search Traversal
You can traverse the binary tree in the same fashion. However binary trees can be traversed differently which can come in handy with binary search trees:

In Order: left (recurse), self, right(recurse): To elaborate a bit further: If the current node has a left child, recursively visit this child. Then, visit the node itself. If the current node has a right child, recursively visit this child.

Pre Order: self, left (recurse), right(recurse)

Post Order:: left (recurse), right(recurse), self
All the different ways of traversing a BST are more or less a ‘hinted DFS’. Meaning in a DFS, if you have multiple children, you just pick whichever you like and just go deeper. However with inorder, preorder, postorder, you pick a certain node first then continue down the tree again in a fashion similar to DFS.
The term ‘order’ might put you off a bit, it’s not top to bottom like a BFS, it’s more about smallest number to biggest. Hence an inorder traversal will start from the bottom left where the smallest item is at and finish at the bottom right where the biggest item is at.
That being said not every binary tree has an order or is a BST. So alternatively as a way to memorize you can think of nodes of just left and right as numbers grow left to right.
Mapping of a Tree to an Array
Mainly two of types of the above traversal types are used for array to BST conversions:
 Levelorder traversal: More accurate, but not necessarily useful. Depends on your needs.
 Inorder traversal: More logical and useful. The most commonly used binary search tree traversal method is inorder:
If we have an array of [1,2,3], we can turn it into a tree as such:
Example 2
2
/ \
1 3
Inorder array: [1,2,3]
levelorder traversal: [2,1,3]
We can also see the same tree as:
2
/ \
1 3
/ \ / \
nil nil nil nil
Inorder array: [nil,1,nil,2,nil,3,nil]
levelorder traversal: [2,1,3,nil,nil,nil,nil]
Example 3:
3
/ \
1 5
\ \
2 6
Inorder array: [1,2,3,5,6]
Levelorder traversal: [3,1,5,nil,2,nil,6]
or alternatively:
3
/ \
1 5
/ \ / \
nil 2 nil 6
/ \ / \
nil nil nil nil
Inorder array: [nil,1,nil,2,nil,3,nil,5,nil,6,nil]
Levelorder traversal: [3,1,5,nil,2,nil,6,nil,nil,nil,nil]
Question
Go back to Example 1 above. Ask yourself how is the inorder & levelorder traversal among all variations of [1,2,3,4]
different from each other?
Click to see answer 👇
 inorder traversal for all will be:
[1,2,3,4]
 levelorder would be different for each.
Use Paper when debugging your mapping/traversal codes.
 Draw a sample case
 Then iterate through it. Just like a debugger. Think you’re pausing and write down values for your properties. Then traverse and repeat.
 Often times the order of traversal becomes more clear on paper and you realize your code isn’t respecting the intended order. My algorithm was correct, yet I was getting a bad result because I the input array I created in my head was incorrect. As soon as I wrote down on paper, I realized where the conversion of the table to array was wrong. I corrected the array and validated that my algorithm works as expected…
 The more you do on paper, the better you get at visualizing things in your head.
Jargon

Traversals:
 BFS
 DFS
 BST
 BST Traversal
 inorder
 preorder
 postorder

Root: The top node.

Leaf: Any node that doesn’t have a left or right node.

Depth of a node: The number of edges from the node to the root node.

Height of a tree: The maximum number of edges from the root node to a leaf node.

Types of BST:
 Balanced tree: A tree in which the heights of the left and right subtrees of any node differ by at most 1. In Example 1, the B,C trees are balanced.
 Full binary tree: A binary tree in which every node has either 0 or 2 children.
 A complete binary tree: A binary tree in which every level, except possibly the last level, is completely filled, and all nodes in the last level are as far left as possible.
 A Degenerate tree: Every nonleaf node has just one child in a binary tree known as a Degenerate Binary tree. Example 1, the A,E trees are degenerate and considered not efficient for sorting.
See here for more.
What’s the benefit of a balanced Tree?
 A balanced tree will allow you to cut the tree into half by having half on its left and the other half on its right. Unlike a degenerate tree where 100% of the remaining nodes is still on the same side. Degenerate trees are bad for doing a binary search tree. They’re more similar to a Linked List or an array.
Helper functions
Summary
 There are different kinds of trees that shouldn’t be confused with one another. When it comes to binary trees, you may question why the inorder of different trees ends up the same. The answer is:, Even though insertion order the insertion order of elements was different, the logic of inorder will always lead to an inorder output.
 A balanced binary search tree is best for searching because you can cut in half.
 Differences of levelorder vs inorder traversal:
 levelorder maintains a 1:1 relationship with its tree visualization. It’s agnostic to order. And is just all about position. Inorder is considerate of order, which is based off of position and logic.
 levelorder can map
nil
elements in an array back to its original position. Inorder isn’t capable of properly mapping nil elements, because then a nil node will not have left/right elements. Think of our[1,nil,3]
tree. If root isnil
then its left and right nodes wouldn’t exist. So you have to remove anynil
element before mapping back.  Levelorder is more generic and applicable to nonbinary trees as well whereas inorder traversal is only applicable to binary search trees.
So choose your traversal/mapping algorithm wisely.
Example:
 You can easily map a
[1,nil,3]
using levelorder mapping to:
1
/ \
nil 3
 However
[1,nil,3]
using an inorder mapping can get mapped to a root node ofnil
, which will create anil
tree.
I was confusing the two traversals and lost a tremendous amount of time, hence this blog post.
Acknowledgements
Shout out to Josh Caswell and Tim Vermeulen for answering my questions so I was able to put this post together.