/*
 * Copyright (C) 2015 Imran Mammadli
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package tree.binary.alter.reflect;

import algorithms.structures.BTreeNode;

public class Solution1
{
	/**
	 * Reflects the generic binary tree horizontally
	 * 
	 * <p>This method constructs a horizontal mirror reflection of a binary tree.
	 * 
	 * @param root the root of the binary tree
	 * @return the horizontal reflection of the binary tree
	 * 
	 * @time <i>O(n)</i>
	 * @space <i>O(h)</i>
	 **/
	public static <E extends Comparable<E>> BTreeNode<E> reflect(BTreeNode<E> root)
	{
		if (root == null)
		{
			return null;
		}
		
		BTreeNode<E> leftSubtree = reflect(root.getLeft());
		BTreeNode<E> rightSubtree = reflect(root.getRight());
		
		root.setLeft(rightSubtree);
		root.setRight(leftSubtree);
		
		return root;
	}
}