# 1457. Pseudo-Palindromic PAths in a Binary Tree

[link](https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/description/?envType=daily-question&envId=2024-01-24)

## Idea
### Outline
- store as pair number in stack with corresponding node, shown as bit
- ex: {2,0} {3,4} {1,4} {3,12} {1,12} {1,6}
- for {2,0}: since 2 is root, we give it **path=0**
- for other branch like {3,4}: we give it **path= parent-path ^ (1<<parent-value)**, that is,
$$1<<2 = 1 \space\space\space shift \space\space\space left \space\space 2 \space\space bit={100}_2=4_{10}$$
- for leaf nodes like {3,12}
- we give it **path= parent-path ^ (1<<parent-value)**
- and check if **path&(path-1)==0**

## Step
1. keep a stack to traverse the tree using DFS
2. store current-path ^ current->value to children node and put these children to stack every time
3. if arrive the leaf(no left and right child), we check if the path&(path-1)==0,
- we want to check if there's only one set when the number represented in bit form
- ex: 0100 will be accepted because $0100 \space \And \space 0011=0000$
- ex: 1111 will be rejected because $1111 \space \And \space 1110=1110$

## Why keep current-path ^ current->value as frequency count?
1. Take 2-3-3 this path for example
2. appear even time: after Xor operation, digit=0
3. appear odd time: after Xor operation, digit=1
4. Since only when there's at most one element has odd frequency in a list can form a palindrome, we keep the count of element in the path. Then check the count when we arrived leaf

## Reference
[bit shift](https://www.86duino.com/?p=1413&lang=TW)