package binaryTree3;
import java.util.*;
import binaryTree2.MainClass.TreeNode;
public class MainClass {
class Node
{
int data;
Node left, right;
Node(int key)
{
data = key;
left = right = null;
}
}
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
// https://practice.geeksforgeeks.org/problems/ancestors-in-binary-tree/1
public static ArrayList Ancestors(Node root, int target) {
ArrayList ans = new ArrayList<>();
isPresent(root, target, ans);
return ans;
}
public static boolean isPresent(Node root, int target, ArrayList ans) {
if(root == null) return false;
if(root.data == target || isPresent(root.left, target, ans) || isPresent(root.right, target, ans)) {
ans.add(root.data);
return true;
}
return false;
}
// https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/submissions/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
if(root.val == p.val || root.val == q.val) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(right == null) return left;
if(left == null) return right;
return root;
}
// public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// ArrayList l1 = new ArrayList<>();
// ArrayList l2 = new ArrayList<>();
// isPresent(root, p.val, l1);
// isPresent(root, q.val, l2);
// int i = l1.size()-1;
// int j = l2.size()-1;
// while(i >= 0 && j >= 0 && l1.get(i).val == l2.get(j).val) {
// i--;
// j--;
// }
// if(i == l1.size()-1) return null;
// return l1.get(i+1);
// }
// public boolean isPresent(TreeNode root, int target, ArrayList ans) {
// if(root == null) return false;
// if(root.val == target || isPresent(root.left, target, ans) || isPresent(root.right, target, ans)) {
// ans.add(root);
// return true;
// }
// return false;
// }
// https://practice.geeksforgeeks.org/problems/binary-tree-to-dll/1
Node prev = null, head = null;
Node bToDLL(Node root) {
bToDLLUtil(root);
return head;
}
void bToDLLUtil(Node root) {
if(root == null) return;
bToDLLUtil(root.left);
if(prev == null) {
head = root;
} else {
root.left = prev;
prev.right = root;
}
prev = root;
bToDLLUtil(root.right);
}
}