//
//  main.cpp
//  test
//
//  Created by MaKai on 2017/3/18.
//  Copyright © 2017年 MaKai. All rights reserved.
//

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include "cmath"
using namespace std;

struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int val){
        this->left = this->right = NULL;
        this->val = val;
    }
};

Node* findSameParent(Node* root, Node* n1, Node* n2);
void findNodePath(string &p, Node* root, Node* node, string s);

int main(int argc, const char * argv[]) {
    
    Node* n1 = new Node(1);
    Node* n2 = new Node(2);
    Node* n3 = new Node(3);
    Node* n4 = new Node(4);
    Node* n5 = new Node(5);
    Node* n6 = new Node(6);
    n1->left = n2;
    n1->right = n4;
    n2->left = n3;
    n2->right = n6;
    n4->right = n5;
    
    cout<<findSameParent(n1, n3, n6)->val<<endl;
    
    return 0;
}


Node* findSameParent(Node* root, Node* n1, Node* n2) {
    
    string s1 = "";
    string s2 = "";
    findNodePath(s1, root, n1, "r");
    findNodePath(s2, root, n2, "r");
    cout<<s1<<" "<<s2<<endl;

    Node* node = root;
    for (int i = 1; i < min(s1.size(), s2.size()); i++) {
        if (s1[i] == s2[i]) {
            if (s1[i] == '0') {
                node = node->left;
            }else{
                node = node->right;
            }
        }else{
            break;
        }
    }
    
    return node;
}

void findNodePath(string &p, Node* root, Node* node, string s){
    if (root == node) {
        p = s;
        return;
    }
    
    if (root->left) {
        findNodePath(p, root->left, node, s.append("0"));
        s.erase(s.end() - 1);
    }
    if (root->right) {
        findNodePath(p, root->right, node, s.append("1"));
    }
}