In this blog, I will share with you what you need to know about tree data structure and how to traverse through trees.
The tree data structure consists of nodes and edges. Each node is connected through edges. Leaf nodes don’t have any children. A tree can consist of multiple subtrees with a similar structure of a parent at the top and the children directly below it. You can get a clear view of a tree data structure through the graph below:
In a non-linear data structure like a tree, we have different ways to reach a node. These include in-order traversal, pre-order traversal, and post-order traversal. The key difference among them is when to visit the root node in relation to the left node and right node.
Below is a list of practice problems from Leetcode about the tree data structure. Practicing these problems will help you better understand what the tree data structure is and how tree traversal works.
https://leetcode.com/problems/binary-tree-preorder-traversal/
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
stack = [root]
if root is None:
return ans
while stack:
cur = stack.pop()
ans.append(cur.val)
if cur.right:
stack.append(cur.right)
if cur.left:
stack.append(cur.left)
return ans
https://leetcode.com/problems/binary-tree-postorder-traversal/
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
stack = [root]
if root is None:
return ans
while stack:
cur = stack.pop()
if cur != None:
stack.append(cur)
stack.append(None)
if (cur.right != None):
stack.append(cur.right)
if (cur.left != None):
stack.append(cur.left)
else:
ans.append(stack.pop().val)
return ans
https://leetcode.com/problems/binary-tree-inorder-traversal/
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
stack = [root]
if root is None:
return ans
while stack:
cur = stack.pop()
if cur != None:
if cur.right != None:
stack.append(cur.right)
stack.append(cur)
stack.append(None)
if cur.left != None:
stack.append(cur.left)
else:
ans.append(stack.pop().val)
return ans
https://leetcode.com/problems/binary-tree-level-order-traversal/
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
ans = []
if root is None:
return ans
q = deque([root])
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(level)
return ans
https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
class Solution:
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
ans = []
if root is None:
return ans
q = deque([root])
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(level)
return ans[::-1]
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
ans = []
if root is None:
return ans
q = deque([root])
left_to_right = True
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if left_to_right:
ans.append(level)
else:
ans.append(level[::-1])
left_to_right = not left_to_right
return ans
https://leetcode.com/problems/n-ary-tree-level-order-traversal/
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
ans = []
if root is None:
return ans
q = deque([root])
while q:
level = []
for _ in range(len(q)):
cur = q.popleft()
level.append(cur.val)
for child in cur.children:
q.append(child)
ans.append(level)
return ans
https://leetcode.com/problems/check-completeness-of-a-binary-tree/
class Solution:
def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
q = deque([root])
zero = False
while q:
cur = q.popleft()
if cur is None:
zero = True
if zero and cur != None:
return False
if cur != None:
q.append(cur.left)
q.append(cur.right)
return True
https://leetcode.com/problems/find-bottom-left-tree-value/
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
q = deque([root])
while q:
cur = q.popleft()
if cur.right:
q.append(cur.right)
if cur.left:
q.append(cur.left)
return cur.val
https://leetcode.com/problems/even-odd-tree/
class Solution:
def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
q = deque([root])
level = 0
while q:
arr = []
for i in range(len(q)):
cur = q.popleft()
arr.append(cur.val)
if level % 2 == 0:
if arr[i] % 2 == 0:
return False
if i > 0 and arr[i] <= arr[i - 1]:
return False
else:
if arr[i] % 2 != 0:
return False
if i > 0 and arr[i] >= arr[i - 1]:
return False
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
level += 1
return True
https://leetcode.com/problems/n-ary-tree-preorder-traversal/
class Solution:
def preorder(self, root: 'Node') -> List[int]:
ans = []
if root is None:
return ans
stack = [root]
while stack:
cur = stack.pop()
if cur != None:
for i in range(len(cur.children) - 1, -1, -1):
stack.append(cur.children[i])
stack.append(cur)
stack.append(None)
else:
ans.append(stack.pop().val)
return ans
https://leetcode.com/problems/n-ary-tree-postorder-traversal/
class Solution:
def postorder(self, root: 'Node') -> List[int]:
ans = []
if root is None:
return ans
stack = [root]
while stack:
cur = stack.pop()
if cur != None:
stack.append(cur)
stack.append(None)
for i in range(len(cur.children) - 1, -1, -1):
stack.append(cur.children[i])
else:
ans.append(stack.pop().val)
return ans
https://leetcode.com/problems/binary-tree-right-side-view/
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
ans = []
if root is None:
return ans
q = deque([root])
while q:
k = len(q)
for i in range(k):
cur = q.popleft()
if i == k - 1:
ans.append(cur.val)
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
return ans
https://leetcode.com/problems/maximum-depth-of-binary-tree/
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
https://leetcode.com/problems/maximum-depth-of-n-ary-tree/
class Solution:
def maxDepth(self, root: 'Node') -> int:
if root is None:
return 0
ans = 1
for child in root.children:
ans = max(self.maxDepth(child) + 1, ans)
return ans
https://leetcode.com/problems/subtree-of-another-tree/
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
if self.sameTree(root, subRoot):
return True
return (root.left != None and self.isSubtree(root.left, subRoot)) or (root.right != None and self.isSubtree(root.right, subRoot))
def sameTree(self, a, b):
if a == None and b == None:
return True
return a != None and b != None and a.val == b.val and self.sameTree(a.left, b.left) and self.sameTree(a.right, b.right)
https://leetcode.com/problems/symmetric-tree/
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
def helper(a, b):
if a is None and b is None:
return True
if a is None or b is None:
return False
return a.val == b.val and helper(a.left, b.right) and helper(a.right, b.left)
return helper(root.left, root.right)
https://leetcode.com/problems/invert-binary-tree/
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None:
return None
temp = self.invertTree(root.right)
root.right = self.invertTree(root.left)
root.left = temp
return root
https://leetcode.com/problems/merge-two-binary-trees/
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if root1 is None and root2 is None:
return None
if root1 is None and root2 is not None:
return root2
if root1 is not None and root2 is None:
return root1
root1.val += root2.val
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)
return root1
https://leetcode.com/problems/balanced-binary-tree/
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
if abs(self.height(root.left) - self.height(root.right)) > 1:
return False
return self.isBalanced(root.left) and self.isBalanced(root.right)
def height(self, root):
if root is None:
return 0
return max(self.height(root.left), self.height(root.right)) + 1
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
class Solution:
def __init__(self):
self.ans = None
def flatten(self, root: Optional[TreeNode]) -> None:
if root is None:
return
self.flatten(root.right)
self.flatten(root.left)
root.right = self.ans
root.left = None
self.ans = root
https://leetcode.com/problems/sum-of-left-leaves/
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
self.ans = 0
def helper(node):
if node is None:
return 0
if node.left != None and node.left.left == None and node.left.right == None:
self.ans += node.left.val
helper(node.left)
helper(node.right)
helper(root)
return self.ans
https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/
class Solution:
def longestConsecutive(self, root: Optional[TreeNode]) -> int:
self.max = 1
def helper(node, cnt):
self.max = max(self.max, cnt)
if node.left:
if node.left.val == node.val + 1:
helper(node.left, cnt + 1)
else:
helper(node.left, 1)
if node.right:
if node.right.val == node.val + 1:
helper(node.right, cnt + 1)
else:
helper(node.right, 1)
helper(root, 1)
return self.max
https://leetcode.com/problems/sum-root-to-leaf-numbers/
class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
def helper(node, num):
if node is None:
return 0
num = num * 10 + node.val
if node.left == None and node.right == None:
return num
return helper(node.left, num) + helper(node.right, num)
return helper(root, 0)
https://leetcode.com/problems/populating-next-right-pointers-in-each-node/
class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
if root == None:
return
q = deque([root])
while q:
k = len(q)
level = []
for _ in range(k):
node = q.popleft()
level.append(node)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
for i in range(len(level) - 1):
level[i].next = level[i + 1]
return root
https://leetcode.com/problems/count-complete-tree-nodes/
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if root == None:
return 0
def dep(node):
if node == None:
return 0
return 1 + dep(node.left)
l, r = dep(root.left), dep(root.right)
if l == r:
return 2 ** l + self.countNodes(root.right)
else:
return 2 ** r + self.countNodes(root.left)
https://leetcode.com/problems/increasing-order-search-tree/
class Solution:
def increasingBST(self, root: TreeNode) -> TreeNode:
dummy = TreeNode(-1)
self.cur = dummy
def dfs(node):
if node == None:
return
dfs(node.left)
self.cur.right = node
node.left = None
self.cur = self.cur.right
dfs(node.right)
dfs(root)
return dummy.right