I looked into the code of inverting binary tree in the internet. But I couldnt what it is doing. Its written in Python. I am a python programmer myself but couldnt understand it.

The snippet is as follows:

def invertTree(root):
    if root:
        root.left, root.right = invertTree(root.right), invertTree(root.left)
        return root

I don't understand this root.left and root.right . Root is the main node in the graph, it will be an integer or a single character. But what does root.left represent in Python? I honestly do not get it.

Update:

My understanding is the node is access like below:

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data
   def PrintTree(self):
      print(self.data)

root = Node(10)
root.PrintTree()

CodePudding user response：

A binary tree can be used to store elements sorted by a key.(Look for the balanced binary tree for more advanced topic.) If the elements are sorted in ascending order, for any subtree T with the root node R, any element in the left branch of R should be smaller than any element in the right branch of R.

This is a heavily modified version of the example code at Invert a Binary Tree by Shivali Bhadaniya.

'''
         5                         5
       /   \                     /   \
      /     \                   /     \           
     3       7    =======>     7       3           
    / \     /                   \     / \
   1   4   6                     6   4   1 
'''
class Node:
    def __init__(self, data):
        self.left = self.right = None
        self.data = data
    def __repr__(self):
        return repr(self.data)

def invert(root):
    left, right = root.left, root.right
    print(['visiting', root, 'swapping', left, right])
    root.left, root.right = right, left
    if left: invert(left)
    if right: invert(right)

root = Node(5)
root.left = node3 = Node(3)
root.right = node7 = Node(7)
node3.left = Node(1)
node3.right = Node(4)
node7.left = Node(6)

invert(root)

This will output the following.

['visiting', 5, 'swapping', 3, 7]
['visiting', 3, 'swapping', 1, 4]
['visiting', 1, 'swapping', None, None]
['visiting', 4, 'swapping', None, None]
['visiting', 7, 'swapping', 6, None]
['visiting', 6, 'swapping', None, None]

In the above example, the tree before calling invert() was sorted in ascending order. After the call, it will be sorted in descending order. That's why the operation is called 'inversion'.

You can understand why the simple recursion of swaping the left child and the right child results in the inversion, by simulating the above example code with a pencil and paper manually. Compare logs with your calculation.

CodePudding user response：

First understand the problem with a diagram..!

Q:- Given binary tree you have to convert binary tree into invert binary tree. Diagram

Class TreeNode: {Initialization of the binary tree}

The key insight here is to realize that in order to invert a binary tree we only need to recursively swap the children. To avoid using a tmp variable, we can do this pythonically by taking advantage of Python's tuple packing and unpacking and do a direct swap:

> class TreeNode:
>      def __init__(self, val=0, left=None, right=None):
>          self.val = val
>          self.left = left
>          self.right = right

> class Solution:
>     def invertTree(self, root):
>         if root:
>             root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
>         return root

Note that if one of the children is null, the condition if root won't be triggered and the swap in the upper level will still be performed (e.g. node has right child but no left child, assigment will be root.left, root.right = root.right, null).

what is root.left doing? Traversing the left subtree of the binary tree

what is root.right doing? Traversing the right subtree of the binary tree.

Note You can access values of root by root.val as you can see the class TreeNode. I have stored the value in val*

Also to learn more about the binary trees basic questions you should do.

(1)Preorder Traversal

(2)Inorder Traversal

(3)Postorder Traversal

Updated Section.!

Q-: How can the root be accessed from the other class.?

A-: Just call it in the main function..!

Main Function

> if __name__="__main__":
>     s=input()
>     root=TreeNode(s)   
>     Solution().invertTree(root) 
>     inorderTraversal(root) # You can print in any other traversal also as the testcases requirements

For more in detail see the driver code (starting from the 18th line {Below Link}): https://practice.geeksforgeeks.org/problems/mirror-tree/1