SWE Prep

Share this post

Invert Binary Tree

sweprep.substack.com

Invert Binary Tree

Sameer Khoja
Apr 14, 2021
Share

Question: Invert a binary tree.

Input:

4

/ \

2 7

/ \ / \

1 3 6 9

Output:

4

/ \

7 2

/ \ / \

9 6 3 1

Solution

Approach 1: Recursive

The inverse of an empty tree is the empty tree. The inverse of a tree with root r, and subtrees right and left, is a tree with root r, whose right subtree is the inverse of left, and whose left subtree is the inverse of right.

See Approach 1

Complexity:

  • Time Complexity: O(n), since each node is visited by the tree once.

  • Space Complexity: O(n)

Share
Top
New

No posts

Ready for more?

© 2023 Sameer Khoja
Privacy ∙ Terms ∙ Collection notice
Start WritingGet the app
Substack is the home for great writing