Wednesday, October 27, 2021
More

    Invert Binary Tree

    Must Read

    Programmerhttp://www.improgrammer.net
    We started this site to inspire young minds to motivate and encourage them towards Programming Language. In this site you will get programming tutorials, tech, programming facts, programming fun and programming blogs.

    binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A leaf node is a special node that has only a value. It marks the end of the tree. We will also define an empty node that contains no value and no branches.

    To invert a binary tree rooted at a node N, Follow this steps.

    1. Invert its left sub-tree.
    2. Invert its right sub-tree.
    3. Change one of its child pointers(say left) to its parent.

    Invert a binary tree.

         4
       /   \
      2     7
     / \   / \
    1   3 6   9

    to

         4
       /   \
      7     2
     / \   / \
    9   6 3   1

    Trivia:
    This problem was inspired by this original tweet by Max Howell:

    Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.


    solution:
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
      public TreeNode invertTree(TreeNode root) {
      if(root == null) return null;
      TreeNode temp = root.left;
      root.left = invertTree(root.right);
      root.right = invertTree(temp);
      return root;
      }
    }

     

    See more: Merge Two Binary tree

    Latest Articles

    More Recipes Like This