Sandbox

Problem Solution First element of preorder will always be the root of the tree. Inorder traversal searches left tree and then right tree, so we can find the root element in the list and divide the list up into left and right side(trees). Now we can build those trees. Repeat this process with the root of left tree, which is the second element in the preorder list. Then use the third element as th..

Problem Solution The nodes need to know their parent node when they connect to the next node. But since there is no parent value in Node class, the code needs to connect nodes by being on the previous level and updating child nodes. Time Complexity O(N) Space Complexity O(1) """ # Definition for a Node. class Node(object): def __init__(self, val=0, left=None, right=None, next=None): self.val = v..

Problem Recursive Solution This problem is somewhat like BFS, except that we need to examine every node on the same level before expanding. Since the first element of a level is a left child of some node, first traverse down the left subtrees and store the values. Then examine the right nodes while coming back up. After coming back to the root, go to the right subtree and examine the left nodes ..

Problem Recursive Solution Time Complexity O(N) Space Complexity O(N) worst case, O(logN) average case (recursive space of tree height) # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def inorderTraversal(self, root): """ :type root: TreeNode :rtype:..