Jul 9

Tree: Level Order Traversal

Visit every node of the tree from top level (root) to the bottom level.

For example, for this tree:

The output will be:

1, 2, 3, 4, 5, 6, 7

Thinking:

If we know the nodes from the upper level, it’s easy to reach the nodes at the lower level.
At each level we need to move horizontally.
At each level, after we move to the right node horizontally, we cannot go back to the previous nodes without tracking them somewhere. So we have to track the previous visited nodes. The least nodes we need to track are the nodes…

Binary Search

When solving a search problem, we should think of binary search whenever the data set is sorted in some way.

Even if the dataset is not sorted, we should still think of binary search if the data is sortable. It depends on if sorting the data first will make a better & faster solution.

Any dataset is sortable if you can directly compare any two items from the dataset, i.e., we should be able to decide which one is “smaller” or which one is “larger”. Examples:

numbers (integer, float, etc)
words (strings): alphabetical order or any other defined comparison
products…

Binary Tree Traversal — Non Recursive

This article talks about recursive solutions of binary tree traversal.

Preorder

Thinking:

Start from the root, visit the parent node before going into any sub-tree.
If the parent has only left child, go to the left.
If the parent has only right child, go to the right.
If the parent has both left and right children, hmm… we must go to the left child first, but we also need to do something to make sure some time later we can still reach the right child (otherwise the right tree is lost). …

Binary Tree Traversal — Recursive

Binary Tree is a special tree structure where every node has no more than two children. Example:

Preorder

Visit the parent node as the first.

Visit the parent node
Visit the left tree
Visit the right tree

Note: it’s visiting the left tree & right tree, not just the left node & right node.

def preorder_traversal(root):
  if not root:
    return
  visit(root)
  preorder_traversal(root.left)
  preorder_traversal(root.right)

If you print out the sequence, the root node must be the first. For the above example, it will be:

1, 2, 4, 5, 3, 6, 7

Inorder

Visit the parent node in the middle.

Visit the…

Nardis

A music lover who can also writes code.

Get the Medium app