Grind75 Notes
  • README
  • week-1
    • Two Sum
    • Valid Parentheses
    • Merge Two Sorted Lists
    • Best Time to Buy and Sell Stock
    • Valid Palindrome
    • Invert Binary Tree
    • Valid Anagram
    • Binary Search
    • Flood Fill
    • Lowest Common Ancestor of a Binary Search Tree
    • Balanced Binary Tree
    • Linked List Cycle
    • Implement Queue using Stacks
  • week-2
    • First Bad Version
    • Ransom Note
    • Climbing Stairs
    • Longest Palindrome
    • Reverse Linked List
    • Majority Element
    • Add Binary
    • Diameter of Binary Tree
    • Middle of the Linked List
    • Maximum Depth of Binary Tree
    • Contains Duplicate
    • Maximum Subarray
  • week-3
    • Insert Interval
    • 01 Matrix
    • K Closest Points to Origin
    • Longest Substring Without Repeating Characters
    • 3Sum
    • Binary Tree Level Order Traversal
    • Clone Graph
    • Evaluate Reverse Polish Notation
  • week-4
    • Course Schedule
    • Implement Trie (Prefix Tree)
    • Coin Change
    • Product of Array Except Self
    • Min Stack
    • Validate Binary Search Tree
    • Number of Islands
    • Rotting Oranges
  • week-5
    • Search in Rotated Sorted Array
    • Combination Sum
    • Permutations
    • Merge Intervals
    • Lowest Common Ancestor of a Binary Tree
    • Time Based Key-Value Store
    • Accounts Merge
    • Sort Colors
  • week-6
    • Word Break
    • Partition Equal Subset Sum
    • String to Integer (atoi)
    • Spiral Matrix
    • Subsets
    • Binary Tree Right Side View
    • Longest Palindromic Substring
    • Unique Paths
    • Construct Binary Tree from Preorder and Inorder Traversal
  • week-7
    • Container With Most Water
    • Letter Combinations of a Phone Number
    • Word Search
    • Find All Anagrams in a String
    • Minimum Height Trees
    • Task Scheduler
    • LRU Cache
  • week-8
    • Kth Smallest Element in a BST
    • Minimum Window Substring
    • Serialize and Deserialize Binary Tree
    • Trapping Rain Water
    • Find Median from Data Stream
    • Word Ladder
    • Basic Calculator
    • Maximum Profit in Job Scheduling
    • Merge k Sorted Lists
    • Largest Rectangle in Histogram
Powered by GitBook
On this page
  • Problem
  • Pseudocode
  • Solution
  • Time and Space Complexity
  1. week-1

Invert Binary Tree

PreviousValid PalindromeNextValid Anagram

Last updated 2 years ago

Problem

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output:
 [4,7,2,9,6,3,1]

Example 2:

Input: root = [2,1,3]
Output:
 [2,3,1]

Example 3:

Input: root = []
Output:
 []

Pseudocode

inverting a tree involves swapping the left and right child nodes
generally
let temp = node.left
node.left = node.right
node.right = temp

in the example for the tree with 3 node height, the left most node is inverted to be the right most node.

two methods to traverse a binary tree. dfs, bfs.

dfs solution
swap left and right nodes in post traversal

bfs solution

Solution

// dfs
var invertTree = function (root) {
  function walk(node) {
    // base condition
    if (!node) {
      return;
    }

    // pre
    // console.log(node.val)
    // recurse
    walk(node.left);
    walk(node.right);
    // post
    let temp = node.left;
    node.left = node.right;
    node.right = temp;
  }

  walk(root);

  return root;
};

//bfs
var invertTree = function(root) {
    if(!root) {
        return null;
    }

    let q = [root];

    while(q.length) {
        const node = q.pop()

        if(node.left) q.push(node.left);
        if(node.right) q.push(node.right);

        let temp = node.left;
        node.left = node.right;
        node.right = temp;
    }

    return root
};

Time and Space Complexity

Time

  • While traversal/searching of BT is usually O(height), inversion requires complete traversal of all inputs, regardless of bfs or dfs. O(N)

  • Total - O(N)

Space

  • Returning the same node length O(N)

  • Total - O(N)

Loading...LeetCode
Logo