Skip to content

Latest commit

 

History

History
231 lines (176 loc) · 5.43 KB

binary-search-tree-traversal.asc

File metadata and controls

231 lines (176 loc) · 5.43 KB
Raw

Binary Tree Traversal

In this section, we are going to focus on depth-first tree traversal.

In Order Traversal

If your tree happens to be a binary search tree (BST), then you can use "in order" traversal to get the values sorted in ascending order. To accomplish this, you have to visit the nodes in a left-root-right order.

If we have the following tree:

         10
       /    \
      5      30
    /       /  \
   4       15   40
 /
3

In-order traverval will return 3, 4, 5, 10, 15, 30, 40.

Check out the implementation:

In-order traversal implementation
link:../../../src/data-structures/trees/binary-search-tree.js[role=include]

This function gets the leftmost element (recursively) and then yields that node, then we go to the right child (if any) and repeat the process. This method will get us the values ordered.

Pre Order Traversal

Pre-order traversal visits nodes in this order root-left-right recursively.

Usage of pre-order traversal:

  • Create a copy of the tree.

  • Get prefix expression on of an expression tree used in the polish notation.

Pre-order traversal implementation
link:../../../src/data-structures/trees/binary-search-tree.js[role=include]

If we have the following tree:

         10
       /    \
      5      30
    /       /  \
   4       15   40
 /
3

Pre-order traverval will return 10, 5, 4, 3, 30, 15, 40.

Post-order Traversal

Post-order traversal goes to each node in this order left-right-root recursively.

Usages of the post-order tree traversal

  • Traversal is used to delete the tree because you visit the children before removing the parent.

  • Get the postfix expression of an expression tree used in the reverse polish notation.

Post-order traversal implementation
link:../../../src/data-structures/trees/binary-search-tree.js[role=include]

If we have the following tree:

         10
       /    \
      5      30
    /       /  \
   4       15   40
 /
3

Post-order traverval will return 3, 4, 5, 15, 40, 30, 10.

Practice Questions

Binary Tree Diameter

BT-1) Find the diameter of a binary tree. A tree’s diameter is the longest possible path from two nodes (it doesn’t need to include the root). The length of a diameter is calculated by counting the number of edges on the path.

Common in interviews at: FAANG

Examples:

/*           1
            / \
           2   3
          / \
         4   5          */
diameterOfBinaryTree(toBinaryTree([1,2,3,4,5])); // 3
// For len 3, the path could be 3-1-2-5 or 3-1-2-4

/*           1
            / \
           2   3
              / \
             4   5
            /     \
           6       7
          /         \
         8           9      */
const array = [1,2,3,null,null,4,5,6,null,null,7,8,null,null,9];
const tree = BinaryTreeNode.from(array);
diameterOfBinaryTree(tree); // 6 (path: 8-6-4-3-5-7-9)

Starter code:

link:../../interview-questions/diameter-of-binary-tree.js[role=include]
Binary Tree from right side view

BT-2) Imagine that you are viewing the tree from the right side. What nodes would you see?

Common in interviews at: Facebook, Amazon, ByteDance (TikTok).

Examples:

/*
 1      <- 1 (only node on level)
 /   \
2     3   <- 3 (3 is the rightmost)
 \
  4       <- 4 (only node on level) */
rightSideView(BinaryTreeNode.from([1, 2, 3, null, 4])); // [1, 3, 4]

rightSideView(BinaryTreeNode.from([])); // []
rightSideView(BinaryTreeNode.from([1, 2, 3, null, 5, null, 4, 6])); // [1, 3, 4, 6]

Starter code:

link:../../interview-questions/binary-tree-right-side-view.js[role=include]