# //Lists are linear but trees are nonlinear 
# //Often working with binary trees and specifically binary search trees 
 
# //SL is techically a special case tree 
 
# //Root: top node of tree
# //Child: node directly connected to another node when moving away from root 
# //Parent: converse notion of child 
# //Siblings: group of node with same parent 
# //Leaf: node with no children 
# //Edge: connection betweeen one node and another (often arrows) 
 
# //Used for HTML DOM, network routing, abstract syntax trees, folder organization, AI, best possible move (decision tree)
 
# //We will focus on binary search tree (can only have at most 2 child nodes)
# //For each node, everything to left is smaller. Right >> bigger
 


class Node: 
  def __init__(self, value): 
    self.value = value 
    self.left = None 
    self.right = None 

class BinarySearchTree: 
  def __init__(self): 
    self.root = None 

  #adds number to correct place 
  def insert(self, value): 
    #creates new Node   
    new_node = Node(value) 
    #start at root 
    #if no root exists, root becomes new_node 
    if self.root == None: 
      self.root = new_node 
      return self 
    
    current = self.root 
    
    while True: 
      #to handle special case where value is same as current node 
      #you can return None or you can add a counter property 
      if value == current.value: 
        return None 
      #check to see if value is less than current 
      if value < current.value: 
        #check to see if there is node to left 
        #if not, add new_node to left 
        if current.left == None: 
          current.left = new_node 
          return self
        #if there is node to left, move to that node and repeat 
        current = current.left 
      #check to see if value is greater than current 
      else: 
        #check to see if there is node to right 
        #if not, add new_node to right 
        if current.right == None: 
          current.right = new_node 
          return self 
        #if there is node to right, move to that node and repeat 
        current = current.right 
  
  #find() returns value while contains() returns boolean 
  #find will point to entire node 
  def find(self, value): 
    #check to see if there is root and if not, we are done! 
    if self.root == None: 
      return False 
    current = self.root 
    found = False 
    
    while current and not found: 
      #if value is less than current 
      if value < current.value: 
        #check to see if there is node to left 
        #if there is, move to that node and repeat 
        current = current.left 
        #if not, we ar edone because current will no longer exist 
      #if value is greater than current 
      elif value > current.value: 
        #check to see if there is node to right 
        #if there is, move to that node and repeat 
        current = current.right 
        #if not, we are done because current will no longer exist 
      else: 
        found = True 
    
    if not found:
      return None 
    return current 
    
  def contains(self, value): 
    if self.root == None: 
      return False 
    current = self.root 
    found = False 
    
    while current and not found: 
      if value < current.value: 
        current = current.left 
      elif value > current.value: 
        current = current.right 
      else: 
        return True 
    return False 
          
t = BinarySearchTree()
t.insert(3)
t.insert(5)
t.insert(2)
t.insert(-1)
t.insert(6)
t.find(6) 
t.contains(6)

# // Insertion and Search: O(log N) VERY GOOD 
# // Not guaranteed if BST is a one sided tree (choose a different root) 
 
 
 
# //      10
# //   5     13
# // 2  7  11  16
 
# // tree = BinarySearchTree()
# // tree.insert(10)
# // tree.insert(5)
# // tree.insert(13)
# // tree.insert(11)
# // tree.insert(2)
# // tree.insert(16)
# // tree.insert(7)
# // tree.find(7) >> will point to node with 7  
# // tree.contains(6) >> False 
 
 
 
 
 
# //Primitive way of making Tree before insert() 
# // tree = BinarySearchTree()
# // tree.root = Node(10)
# // tree.root.right = Node(15)
# // tree.root.left = Node(7)
# // tree.root.left.right = Node(9)

class Tree(object):
    def __init__(self, value, left=None, right=None):
        self.val = value
        self.left = left
        self.right = right 
 
tx = Tree(4, Tree(1, Tree(-2, None, Tree(3, None, None))), Tree(3, Tree(1, None, None), Tree(2, Tree(-4, None, None), Tree(-3, None, None))))


def find_paths(root, required_sum):
    allPaths = []
  
    def find_paths_recursive(currentNode, required_sum, currentPath, allPaths):
      if currentNode is None:
        return
    
      # add the current node to the path
      currentPath.append(currentNode.val)
    
      # if the current node is a leaf and its value is equal to required_sum, save the current path
      if currentNode.val == required_sum and currentNode.left is None and currentNode.right is None:
        allPaths.append(list(currentPath))
      else:
        # traverse the left sub-tree
        find_paths_recursive(currentNode.left, required_sum -
                             currentNode.val, currentPath, allPaths)
        # traverse the right sub-tree
        find_paths_recursive(currentNode.right, required_sum -
                             currentNode.val, currentPath, allPaths)
    
      # remove the current node from the path to backtrack,
      # we need to remove the current node while we are going up the recursive call stack.
      del currentPath[-1]
    
    find_paths_recursive(root, required_sum, [], allPaths)
    
    return allPaths

find_paths(tx, 5)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        #order of first two conditionals is important 
        if not subRoot: return True 
        if not root: return False 
        if self.sameTree(root, subRoot): return True 
        
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
        
        
    def sameTree(self, s, t): 
        if not s and not t: return True 
        if s and t and s.val == t.val: 
            return self.sameTree(s.left, t.left) and self.sameTree(s.right, t.right) 

        return False 
        
        

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q: return True 
        if not p or not q: return False 
        if p.val != q.val: return False 
        
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        

using System;
using System.Collections.Generic;
using System.Xml.Linq;
class Program {
	static void Main( ) {
		XDocument employeeDoc = new XDocument(
			new XElement("Employees",
				new XElement("Employee",
					new XElement("Name", "Bob Smith"),
					new XElement("PhoneNumber", "408-555-1000")),
				new XElement("Employee",
					new XElement("Name", "Sally Jones"),
					new XElement("PhoneNumber", "415-555-2000"),
					new XElement("PhoneNumber", "415-555-2001")
				)
			)
		);//Get first child XElement named "Employees"
		XElement root = employeeDoc.Element("Employees");
		IEnumerable<XElement> employees = root.Elements();
		foreach (XElement emp in employees){
			//Get first child XElement named "Name"
			XElement empNameNode = emp.Element("Name");
			Console.WriteLine(empNameNode.Value);
			//Get all child elements named "PhoneNumber"
			IEnumerable<XElement> empPhones = emp.Elements("PhoneNumber");
			foreach (XElement phone in empPhones)
				Console.WriteLine($" { phone.Value }");
		}
	}
}

using System;
using System.Xml.Linq; // This namespace is required.
class Program
{
	static void Main( )
	{
		XDocument employeeDoc =	new XDocument(
		new XElement("Employees",
			new XElement("Employee",
				new XElement("Name", "Bob Smith"),
				new XElement("PhoneNumbers",
					new XElement("Home", "408-555-1000"))),
			new XElement("Employee",
				new XElement("Name", "Sally Jones"),
				new XElement("PhoneNumbers",
					new XElement("Home", "415-555-2000"),
					new XElement("Cell", "415-555-2001")))));
		Console.WriteLine(employeeDoc); // Displays the document
	}
}

from sklearn.model_selection import train_test_split,cross_val_predict,StratifiedKFold
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import classification_report,roc_auc_score,roc_curve
from imblearn.pipeline import Pipeline as imbPipe
from imblearn.over_sampling import SMOTE
from sklearn.ensemble import VotingClassifier
from sklearn.linear_model import LogisticRegression, SGDClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.svm import LinearSVC, SVC
from sklearn.neighbors import KNeighborsClassifier



X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42,
                                                    shuffle=True, stratify  = y)

dct = DecisionTreeClassifier(random_state=42)
sgd = SGDClassifier(random_state=42)
log = LogisticRegression(random_state=42)
svm_rbf = SVC(kernel="rbf", random_state=42)
svm_lin = LinearSVC(loss="hinge")
knn=KNeighborsClassifier()

kfold = StratifiedKFold(n_splits=4, shuffle=True, random_state=42)


Voting_pipeline = imbPipe([
    
    ("scaler", StandardScaler()),
    ("smote", SMOTE(random_state=42,n_jobs=-1)),
    ("voting", VotingClassifier(estimators=[("dct", dct),
                                            ("sgd", sgd),
                                            ("svm_rbf", svm_rbf),
                                            ("smv_lin", svm_lin),
                                            ("knn",knn),
                                            ("log", log)],voting="hard",n_jobs=-1))
])


y_pred = cross_val_predict(Voting_pipeline, X_train, y_train, cv = kfold)
print(classification_report(y_train, y_pred))