Teaching Kids Programming: Videos on Data Structures and Algorithms
Given the root of a binary tree, return the inorder traversal of its nodes’ values.
Example 1:
Input: root = [1,null,2,3]
Output: [1,3,2]Example 2:
Input: root = []
Output: []Example 3:
Input: root = [1]
Output: [1]Example 4:
Input: root = [1,2]
Output: [2,1]Example 5:
Input: root = [1,null,2]
Output: [1,2]Constraints:
The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100Follow up: Recursive solution is trivial, could you do it iteratively?
Recursive Inorder Traversal Algorithm for Binary Tree
The Inorder traverses the left tree first, and then the current node, and then recursively the right tree.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: ans = [] def dfs(root): if root is None: return nonlocal ans dfs(root.left) ans.append(root.val) dfs(root.right) dfs(root) return ans |
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
ans = []
def dfs(root):
if root is None:
return
nonlocal ans
dfs(root.left)
ans.append(root.val)
dfs(root.right)
dfs(root)
return ansRecursive Inorder traversal algorithm takes O(N) time and O(N) space due to stack implied by Recursion.
Inorder Traversal Algorithm using Iterative Algorithm
We can use a stack to perform the inorder traversal. We push the left nodes as many as possible to the stack, pop one, and then go to its right tree.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: if root is None: return [] ans = [] st = [] cur = root while cur or st: while cur: st.append(cur) cur = cur.left cur = st.pop() ans.append(cur.val) cur = cur.right return ans |
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
ans = []
st = []
cur = root
while cur or st:
while cur:
st.append(cur)
cur = cur.left
cur = st.pop()
ans.append(cur.val)
cur = cur.right
return ansThe time and space complexity is O(N).
Tree Inorder Traversal Algorithms:
- Teaching Kids Programming – Algorithms to Find the Inorder Successor of a Binary Search Tree
- Compute the Inorder Successor of a Binary Tree
- Teaching Kids Programming – Construct Binary Tree From Pre/Inorder Traversals
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: GoLang: A Command-Line HTTP Client Tool to Grab URL Contents
Next Post: GoLang: Implement Trie (Prefix Tree)
