Shortest path in binary tree, C++ (gcc)

Shortest path in binary tree

#include <iostream>
#include <list>
#include <vector>
using namespace std;

struct BinTree {
  
    int data;
    BinTree *left;
    BinTree *right;
    
    BinTree(int d, BinTree* l, BinTree* r): data(d), left(l), right(r) {}
    
};

BinTree* LowestCommonAncestor(BinTree* root, int a, int b, list<BinTree*>& stackA, list<BinTree*>& stackB, bool& foundBoth) {
 
    if (!root)
        return NULL;
    
    
    if (a == root->data) {
        stackA.push_front(root);
        return root;
    }
    if (b == root->data) {
        stackB.push_front(root);
        return root;
        
    }
    
    
    BinTree* lhcLeft = LowestCommonAncestor(root->left, a, b, stackA, stackB, foundBoth);
    BinTree* lhcRight = LowestCommonAncestor(root->right, a, b, stackA, stackB, foundBoth);
    
    
    if (lhcLeft && lhcRight) {
        stackA.push_front(root);
        foundBoth = true;
        return root;   
    }
    
    if (lhcLeft) {

if (!foundBoth)
        if (lhcLeft->data == a)
            stackA.push_front(root);
        else
            stackB.push_front(root);

return lhcLeft;
    }
    if (lhcRight) {

if (!foundBoth)
        if (lhcRight->data == a)
            stackA.push_front(root);
        else
            stackB.push_front(root);
        
        return lhcRight;
    }
    
    return NULL;
    
}

void printStack(list<BinTree*>& l) {
    
    for (auto it = l.begin(); it != l.end(); ++it)
        cout << (*it)->data << " ";
    
}

//           4
//         /   \
//        2     8   
//       / \   / \   
//      1  3  6   9
//           / \
//          5   7

int main()
{
    BinTree *h = new BinTree(7, NULL, NULL);
    BinTree *j = new BinTree(5, NULL, NULL);
    BinTree *g = new BinTree(9, NULL, NULL);
    BinTree *f = new BinTree(6, j, h);
    BinTree *e = new BinTree(3, NULL, NULL);
    BinTree *d = new BinTree(1, NULL, NULL);
    BinTree *c = new BinTree(8, f, g);
    BinTree *b = new BinTree(2, d, e);
    BinTree *a = new BinTree(4, b, c);
    
    list<BinTree*> sa,sb;
    bool foundBoth = false;;
    
    cout << LowestCommonAncestor(a, 1, 5, sa, sb, foundBoth)->data << endl;

sa.reverse();
    list<BinTree*> path;
    path.insert(path.end(), sa.begin(), sa.end());
    path.insert(path.end(), sb.begin(), sb.end());
    
    
    printStack(path);
  
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development