LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal
Algorithm explanation & javascript example walkthrough.
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
Intuition: When looking at any node in the in-order array, nodes to the left are part of the left sub-tree. Nodes to it's right are the right sub-tree. The number of left nodes is how far to skip ahead in the pre-order array to find the right child. This algorithm repeats recursively, updating a low/upper bounds tracking the context of the tree, until the two pointers cross, which base cases it out.
https://leetcode.com/problems/constru...
SOCIAL
----------------------------------------------------------------------------------------------------------------
Instagram: / joshribakoff
Twitter: / joshribakoff
Github: https://github.com/joshribakoff
LinkedIn: / josh-ribakoff