Sep 26, 2022
94. Binary Tree Inorder Traversal
Leetcode #: 94
Name: Binary Tree Inorder Traversal
Difficulty: Easy
Companies asked: Amazon, Apple, Google, LinkedIn, Meta, Microsoft, Uber
Url: https://leetcode.com/problems/binary-tree-inorder-traversal/
Prompt
You’re given the root of a binary tree and it’s your task to return all the nodes within the binary tree inorder.
Approach
This problem is testing your knowledge of whether if you know how to code out an inorder traversal algorithm for a Binary Tree. The inorder traversal algorithm for a binary tree is quite straightforward once you’ve seen it. I’ll be writing the inorder traversal algorithm recursively since we’re dealing with a tree and a tree might have more than 1 level in which a recursive algorithm really comes into handy.
For this problem, as we traverse the Binary Tree inorder, we also want to append all the node values into an array so we’ll go ahead and instantiate an empty array.
Base Case
Our base case is going to be checking if the root is null which basically means that during our inorder traversal algorithm, we ended up at a null node or an empty tree. In that scenario, we just want to simply return.
if not root:
returnRecursive Case
An inorder traversal is different from its counterparts (preorder & postorder) by having our action (in this case, appending to an array) in between the recursive calls of our left & right subtrees respectively. This is because just like how the name of the traversal algorithm implies (inorder), we want to append to our array as if it’s literally in order or in sorted order.
inorder(root.left, arr)
arr.append(root.val)
inorder(root.right, arr)Code
Thank you for reading!
In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.
If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com
