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

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 in-order, pre-order, post-order, 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 in-order 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:

  • Level-order traversal: More accurate, but not necessarily useful. Depends on your needs.
  • In-order traversal: More logical and useful. The most commonly used binary search tree traversal method is in-order:

If we have an array of [1,2,3], we can turn it into a tree as such:

Example 2

      2 
     / \
    1   3

In-order array: [1,2,3]
level-order traversal: [2,1,3]

We can also see the same tree as:

         2 
       /  \
      1     3
    /  \   /  \
  nil nil nil nil

In-order array: [nil,1,nil,2,nil,3,nil]
level-order traversal: [2,1,3,nil,nil,nil,nil]

Example 3:

        3
      /   \
     1      5
      \      \
       2      6

In-order array: [1,2,3,5,6]
Level-order traversal: [3,1,5,nil,2,nil,6]

or alternatively:

          3
       /     \
     1          5
   /  \       /  \
nil    2    nil   6
     /  \        /  \
  nil  nil    nil  nil

In-order array: [nil,1,nil,2,nil,3,nil,5,nil,6,nil]
Level-order traversal: [3,1,5,nil,2,nil,6,nil,nil,nil,nil]

Question

Go back to Example 1 above. Ask yourself how is the in-order & level-order traversal among all variations of [1,2,3,4] different from each other?

Click to see answer 👇
  • in-order traversal for all will be: [1,2,3,4]
  • level-order 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
      • in-order
      • pre-order
      • post-order

  • 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 non-leaf 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

  • Tree Printer. See here
  • Array to ‘Balanced Height Binary Tree Search’ Convertor
    • level-ordered array to tree. See here. Creates a tree exactly based on its input.
    • in-order array to tree: See here. Only t balanced tree. Won’t create any other representation of the tree.
  • Traversals. See here

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 in-order of different trees ends up the same. The answer is:, Even though insertion order the insertion order of elements was different, the logic of in-order will always lead to an in-order output.
  • A balanced binary search tree is best for searching because you can cut in half.
  • Differences of level-order vs in-order traversal:
    • level-order maintains a 1:1 relationship with its tree visualization. It’s agnostic to order. And is just all about position. In-order is considerate of order, which is based off of position and logic.
    • level-order can map nil elements in an array back to its original position. In-order 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 is nil then its left and right nodes wouldn’t exist. So you have to remove any nil element before mapping back.
    • Level-order is more generic and applicable to non-binary trees as well whereas in-order 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 level-order mapping to:
    1
  /   \
nil    3
  • However [1,nil,3] using an in-order mapping can get mapped to a root node of nil, which will create a nil 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.