Language & Programming / LeetCode · Destination 3 of 6
Graphs
11 solutions from leetcode_problems (trees_and_tries.py), shown as written. Open any entry to read the code.
11 entries
On this page: Traversal and depth problems. There are no general graph problems in the source yet; trees are the connected, acyclic case, so these breadth- and depth-first searches are the same graph searches.
From l2mcgrat/leetcode_problems ↗ at commit f9cf5a8. Code is shown as written, test lines included; this site never runs it.
Every module, function and class is also listed in the source index.
Index
- Pre-Order Traversal
- In-Order Traversal
- Post-Order Traversal
- Pre-Order Traversal
- In-Order Traversal
- Post-Order Traversal
- Post-Order Traversal (Hack Method)
- Level-Order Traversal (BFS)
- Maximum Depth of Binary Tree (Just Reuse Level Order Traversal, return len(ans))
- Maximum Depth of Binary Tree (The Simpler Way, Lower Space Complexity)
- Binary Search Tree Iterator (Recursive Inorder Traversal to Build List)
Trees and Tries · Binary Trees Iterative Traversal
Pre-Order Traversal
root = None
def preorderTraversal_Iterative(root):
'''
Pre Order Traversal is basically go left until you can't then after reaching the
end of a branch then go right if possible and continue going left until you can't
and backtrack when you can't go left or right anymore... idk its simple but hard to explain
stack ensures you follow the most recent root node added if its not None (end of branch)
so when we add the left node if it exists we will visit it next, and again, and again,
until you go as far as you can go in the left branch then you go right and then backtrack
to previous nodes and then go right and repeat the left priority process
summary: top --> bottom left --> right
'''
if not root: # for when theres no tree to begin with lol
return []
stack = [root] # for DFS process
ans = [] # root.val values
while stack:
root = stack.pop()
ans.append(root.val)
if root.right:
stack.append(root.right)
if root.left:
stack.append(root.left)
return ansIn-Order Traversal
root = None
def inorderTraversal_Iterative(root):
'''
this is a level more difficult than Pre-Order Traversal
because it appends values in the order of what is left most
then what the root above is, before going right next
stack gets built up while moving thru nodes to the bottom left
re-visits parent node when child node is None or is called from the stack
proceeds to go right, then resumes going left building up stack
summary: bottom left --> root --> right
append values from left to right via DFS algorithm
'''
stack = []
ans = []
while stack or root: # why {or root}? compared to Pre-Order Traversal
while root: # because root node existing is a pre-requisite fir stack build-up
stack.append(root) # stack gets built up by appending not None child roots
root = root.left # loop ends when a child node turns out to be None or Null
root = stack.pop() # root node (or parent node) is popped from the stack
ans.append(root.val) # value is appended from order of left to right in tree strucuture
root = root.right # finally node focused on next becomes the next right node
return ansPost-Order Traversal
root = None
def levelorderTraversal_Iterative(root):
'''
use queue DS for BFS to access one level at a time
when there are no more levels queue will be empty and while loop will stop
ans will be returned listing from left to right every val for nodes on each level
summary: bottom left --> right --> root
'''
ans = []
if not root:
return ans
level = 0
queue = [root]
while queue:
ans.append([])
for i in range(len(queue)):
root = queue.pop(0)
ans[level].append(root.val)
if root.left:
queue.append(root.left)
if root.right:
queue.append(root.right)
level += 1
return ansTrees and Tries · Binary Trees Recursive Traversal
Pre-Order Traversal
root = None
def preorderTraversal_Recursive(root):
'''
summary: root --> bottom left --> right
'''
ans = []
if not root:
return ans
def helper(root):
if root:
ans.append(root.val)
helper(root.left)
helper(root.right)
helper(root)
return ansIn-Order Traversal
root = None
def inorderTraversal_Recursive(root):
'''
summary: bottom left --> root --> right
'''
ans = []
if not root:
return ans
def helper(root):
if root:
helper(root.left)
ans.append(root.val)
helper(root.right)
helper(root)
return ansPost-Order Traversal
root = None
def postorderTraversal_Recursive(root):
'''
summary: bottom left --> right --> root
'''
ans = []
if not root:
return ans
def helper(root):
if root:
helper(root.left)
helper(root.right)
ans.append(root.val)
helper(root)
return ansPost-Order Traversal (Hack Method)
root = None
def postorderTraversal_Recursive_Hack(root):
'''
hack relies on copying the pre-order traversal
and reversing the tranversal anser
summary: bottom left --> right --> root
'''
ans = []
if not root:
return ans
def helper(root):
if root:
ans.append(root.val)
helper(root.right)
helper(root.left)
helper(root)
return ans[::-1]Level-Order Traversal (BFS)
root = None
def levelorderTraversal_Recursive(root):
'''
summary: bottom left --> right --> root
'''
ans = []
if not root:
return ans
def helper(root, level):
if len(ans) == level: # append new empty list if needed
ans.append([])
ans[level].append(root.val) # add this levels root.val to level list
if root.left: # go left until you reach a None node
helper(root.left, level + 1)
if root.right:
helper(root.right, level + 1) # go right until you reach a None node
helper(root, 0)
return ansTrees and Tries · Various Binary Tree Problems
Maximum Depth of Binary Tree (Just Reuse Level Order Traversal, return len(ans))
root = None
def maxDepth_BFS(root):
'''
Just Return the Length of the Array of Arrays to Determine Depth
BFS Traversal (or just level order traversal)
'''
ans = []
if not root:
return 0
def helper(root, level):
if len(ans) == level: # append new empty list if needed
ans.append([])
ans[level].append(root.val) # add this levels root.val to level list
if root.left: # go left until you reach a None node
helper(root.left, level + 1)
if root.right:
helper(root.right, level + 1) # go right until you reach a None node
helper(root, 0)
return len(ans)Maximum Depth of Binary Tree (The Simpler Way, Lower Space Complexity)
root = None
def maxDepth_DFS(self, root):
'''
DFS Traversal while recording maximum depth along the way on each side
Similar to Dynamic Programming, Explore All (Both) Options, return the max
'''
if not root:
return 0
l_depth = self.maxDepth_DFS(root.left)
r_depth = self.maxDepth_DFS(root.right)
return max(l_depth, r_depth) + 1Trees and Tries · Binary Search Tree
Binary Search Tree Iterator (Recursive Inorder Traversal to Build List)
class BSTIterator:
def __init__(self, root):
self.traversal = []
self.index = -1
self.inorder(root)
def inorder(self, root):
if not root:
return None
self.inorder(root.left)
self.traversal.append(root.val)
self.inorder(root.right)
def next(self) -> int:
self.index += 1
return self.traversal[self.index]
def hasNext(self) -> bool:
return self.index < len(self.traversal) - 1