Q$)$ Given a binary tree, count the total number of magic parents, where a node which is not NULL and has both left and right children and the sum of the number of nodes in the left subtree is odd and that of right subtree is even $($or sum of nodes in the left subtree as even and right subtree as odd$)$ should be considered as a magic parent. Node $1$ is always the Root node

Input format:

The node$\_$number string$($representing the relative position of the node wrt root node,i$.$e node $1).$

E$.$g:

This is representing a tree having a root node as $1$ and $2$ is the left child of node $1$ and $3$ is the right child of node $1$ and $5$ is the left child of node $3.$

$2$ L

$3$ R

$5$ RL

SOLUTION $-$

class TreeNode:

def $\_\_$init$\_\_($self$,$ val$=0)$:

self.val $=$ val

self.left $=$ None

self.right $=$ None

def build$\_$tree$($instructions$)$:

nodes $=\{1$: TreeNode$(1)\}$ # Root node

for instruction in instructions:

node$\_$val, path $=$ instruction.split$()$

node$\_$val $=$ int$($node$\_$val$)$

current $=$ nodes$[1]$ # Start from root

# Traverse the path to insert the node in correct position

for direction in path$[$:$-1]$: # Traverse to the parent node

if direction $==\text{'}$L$\text{'}$:

if current.left is None:

current.left $=$ TreeNode$()$

current $=$ current.left

elif direction $==\text{'}$R$\text{'}$:

if current.right is None:

current.right $=$ TreeNode$()$

current $=$ current.right

# Insert the node at the correct position $($last step$)$

if path$[-1]==\text{'}$L$\text{'}$:

current.left $=$ TreeNode$($node$\_$val$)$

elif path$[-1]==\text{'}$R$\text{'}$:

current.right $=$ TreeNode$($node$\_$val$)$

# Save the node for further use

nodes$[$node$\_$val$]=$ current.left if path$[-1]==\text{'}$L$\text{'}$ else current.right

return nodes$[1]$

def count$\_$subtree$\_$nodes$($node$)$:

if node is None:

return $0$

# Recursively count nodes in left and right subtrees

left$\_$count $=$ count$\_$subtree$\_$nodes$($node$.$left$)$

right$\_$count $=$ count$\_$subtree$\_$nodes$($node$.$right$)$

# Check if the current node is a magic parent

if node.left is not None and node.right is not None:

if $($left$\_$count $\%2==0$ and right$\_$count $\%2==1)$ or $($left$\_$count $\%2==1$ and right$\_$count $\%2==0)$:

count$\_$subtree$\_$nodes.magic$\_$parents $+=1$

# Return total nodes in the subtree rooted at current node

return left$\_$count $+$ right$\_$count $+1$

def count$\_$magic$\_$parents$($instructions$)$:

# Build the tree from input instructions

root $=$ build$\_$tree$($instructions$)$

# Initialize a variable to count magic parents

count$\_$subtree$\_$nodes.magic$\_$parents $=0$

# Count the number of nodes in subtrees and check for magic parents

count$\_$subtree$\_$nodes$($root$)$

return count$\_$subtree$\_$nodes.magic$\_$parents

# Input example:

instructions $=["2$ L$","3$ R$","5$ RL$"]$

result $=$ count$\_$magic$\_$parents$($instructions$)$

print$($result$)$ # Output will be the number of magic parents