Invert Binary Tree Editorial

Practice Problem Link: Invert Binary Tree

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a binary tree, invert it.

Tree Inversion means that the left child becomes the right child and vice versa. This happens recursively for the subtrees.

Approach (BFS)

Traverse the given tree using level order traversal and swap the left and right child of each node.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++ 

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/

void invertTree(Node* root) {
    queue<Node*> treeNodes;
	treeNodes.push(root);
	while (!treeNodes.empty()) {
		Node* currNode = treeNodes.front();
		treeNodes.pop();
		Node* tempNode = currNode->left;
		currNode->left = currNode->right;
		currNode->right = tempNode;
		if (currNode->left != NULL) {
			treeNodes.push(currNode->left);
		}
		if (currNode->right != NULL) {
			treeNodes.push(currNode->right);
		}
	}
}

Java

/* This is the Node class definition

class Node {
	public Node left;
    public Node right;
    int data;

    Node(int data) {
        this.data = data;
    }
}
*/

class Solution {
	void invertTree(Node root) {
    	Queue<Node> treeNodes = new LinkedList<Node> ();
		treeNodes.add(root);
		while (!treeNodes.isEmpty()) {
			Node currNode = treeNodes.peek();
			treeNodes.poll();
			Node tempNode = currNode.left;
			currNode.left = currNode.right;
			currNode.right = tempNode;
			if (currNode.left != null) {
				treeNodes.add(currNode.left);
			}
			if (currNode.right != null) {
				treeNodes.add(currNode.right);
			}
		}
	}
}

Approach (DFS)

The idea is to recursively invert each node's left and right subtree and then swap the left and right child of that node.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++ 

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/

Node* invertTreeUtil(Node* root) {
	if(root == NULL) {
		return root;
	}
	Node* right = invertTreeUtil(root->right);
	Node* left = invertTreeUtil(root->left);
	root->left = right;
	root->right = left;
	return root;
}
void invertTree(Node* root) {
	invertTreeUtil(root);
}

Java

/* This is the Node class definition

class Node {
	public Node left;
    public Node right;
    int data;

    Node(int data) {
        this.data = data;
    }
}
*/

class Solution {
	Node invertTreeUtil(Node root) {
		if(root == null) {
			return root;
		}
		Node right = invertTreeUtil(root.right);
		Node left = invertTreeUtil(root.left);
		root.left = right;
		root.right = left;
		return root;
	}

	void invertTree(Node root) {
		invertTreeUtil(root);
	}
}