Invert a Binary Search Tree

Binary TreeDepth-First SearchRecursionTree

Given the root of a binary search tree (BST), invert it so that the left and right children of all nodes are swapped around their parent. After inversion, every parent node should still maintain its position, but the left child must contain the value greater than the parent, and the right child the value less than the parent. Provide the inorder traversal of the inverted BST.

Example 1

Input

[
  4,
  2,
  7,
  1,
  3,
  6,
  9
]

Output

[9,7,6,4,3,2,1]

Explanation. Inverting the tree swaps every left and right child. Inorder traversal of the inverted tree should give descending order.

Example 2

Input

[
  2,
  1,
  3
]

Output

[3,2,1]

Explanation. Inverting a small tree where root 2 swaps its left and right child nodes (1 and 3). Inorder traversal of inverted gives descending order.

Example 3

Input

[
  1
]

Output

[1]

Explanation. A single-node tree remains unchanged after inversion. Inorder traversal still presents the single node.

Follow-up: Can you perform the inversion in-place without using additional memory for another tree?

Constraints:

The number of nodes in the given tree will be between 1 and 5000. Each node value is unique within the tree and between 0 and 10000 inclusively.

Views: 2