Problem Statement-
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Understanding the problem-
It's a really standard problem: one of the DFS traversals.
Intuition-
In this traversal, for any subtree, we first choose left node, root, then right node. Let's see the approaches.
Solution: Approach 1- Recursion
Time Complexity: O(n)
Space: O(n)
Approach 2: Iterative
-> Uses stack to store the nodes.
-> Pick the root node
-> go to left most node, push all them in stack
-> Move to right subtree.
Time Complexity: O(n)
Space: O(n)
Approach 3: Morris Traversal
Basically it's the process of making the tree, skewed.
-> Pick the root node
-> Add it to the left most node at every step.
Time Complexity: O(n)
Space: O(1)
That's a wrap!
If you enjoyed this thread:
1. Follow me @Iampatelajeet for,
💻 Coding,
🌐 Case Studies,
👻 free ka gyaan,
🤖 tech stuffs and
😉 coding memes 2. RT is appreciated, share and let everyone be consistent. Start the practice challenge with me.
Problem Statement -
Given the root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it.
Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.
@LeetCode Problem Statement-
Given an n-ary tree, return the level order traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
@LeetCode Understanding the problem-
Usually, we're given tree problems which has left and right child but here is something different. For any node, it's child are given in form of node arrays. It means now any node can have more than 2 child also.
We've to find level order traversal.
Approach 1:
-> we're given a set of strings, let's do it for one string to compare with given pattern.
-> For any string to a pattern of given 'pattern' string,
-> Both length must be equal
-> The number of unique characters must be equal