---
# System prepended metadata

title: LeetCode 1457
tags: [binary tree, Palindromic, DFS, LeetCode]

---

# 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
![圖片](https://hackmd.io/_uploads/S1AiQlx9a.png)
- 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**
    ![圖片](https://hackmd.io/_uploads/H1RJikgca.png)
- 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}$$
    ![圖片](https://hackmd.io/_uploads/HJ5goye9p.png)
- for leaf nodes like {3,12}
    ![圖片](https://hackmd.io/_uploads/BkUphJx96.png)
    - 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
    ![圖片](https://hackmd.io/_uploads/HkpwOglqa.png)
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)