Recursion, trees, data structures
Invert a binary tree.
For example, suppose you have the following tree:
This is a classic recursion problem. These types can be identified by manually reviewing several cases. This is usually a good practice as it helps with debugging and resolving edge cases.
This is marked as a medium issue. It’s actually around the lower end of the medium range. Solving such problems requires understanding data structures/processes.
If you look at this example, you can see that the process is basically swapping left and right nodes. If we examine the binary trees themselves, we can see that they are symmetric. There is no difference between the implementation of right and left nodes. A binary tree node is defined as:
Node(val, Node Left, Node Right). Node can be either a node or none. This implementation of self-reference is why recursion works so well with trees.
Back to the problem. How do I flip the tree? Simply swap the node’s two children, then swap the node with its siblings. Use paper and pen and work through small examples to convince yourself that it will work.
def invert(node):if not node:
return node
left = invert(node.left)
right = invert(node.right)
node.left, node.right = right, left
return node
This problem is not that difficult once you know the trick. Many easy medium problems are that way.If you have any questions, please feel free to contact us
Save time, energy, and money by reviewing all these videos, courses, products, and “coaches” and easily finding one that meets all your needs in one place. “Simplify technology”! Stay on the cutting edge of the AI, software engineering, and technology industry with expert insights, tips, and resources. Click this link to get 20% off for new subscribers. Subscribe today to simplify your technology journey!
With this discount, the price will go down –
800 INR (10 USD) → 640 INR (8 USD)/month
8000 INR (100 USD) → 6400 INR (80 USD)/year (533 INR/month)
Use the links below to check out my other content, learn more about tutoring, contact me about a project, or just say hi.
Click here for short snippets about technology, AI, and machine learning
AI Newsletter – https://artificialintelligencemadesimple.substack.com/
My Grandma’s Favorite Technology Newsletter – https://codinginterviewsmadesimple.substack.com/
Check out my other articles on Medium. : https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Contact me on LinkedIn. Let’s connect: https://rb.gy/m5ok2y
My Instagram: https://rb.gy/gmvuy9
My Twitter: https://twitter.com/Machine01776819