Binary tree

[user42]

hi, I am supposed to write a program that has a function of type const (min_depth_leaf)and that function gets a const that points to the root of a binary tree,
the function is supposed to return a const(leaf) that is pointing to the address of the closest leaf to the root of a tree.
I am having trouble with the function closest_leaf_to_root, this function is supposed to find the closest leaf to the root and it should be recursive(I think) I don't really know where to begin with this function and would be grateful for help
if there are and questions or if something wasn't explained well please ask
thanks in advance!

[user42]

#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <fstream>
#include <new>

//------------------------------------using----------------------------------//
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::nothrow;
//------------------------------------struct---------------------------------//
struct Node {
    int _data;
    struct Node *_left,*_right;
};
//------------------------------------prototype------------------------------//

struct Node *build_tree();
void insert_into_tree(int num,struct Node *&root);
const Node * min_depth_leaf(const struct Node* root);
void closest_leaf_to_root(const Node *root,int counter,int temp_counter,const Node *leaf);
void check_allocated(const struct Node *root);
void free_tree(struct Node *root);

//------------------------------------main-----------------------------------//
int main()
{
    struct Node *root;
    root=build_tree();
    free_tree(root);
    return EXIT_SUCCESS;
}
//----------------------------------function---------------------------------//
struct Node * build_tree()
{
    struct Node *root=NULL;
    int num;

    cin>>num;

    while(num!=0)  //change to eof
    {
        insert_into_tree(num,root);
        cin >>num;
    }
    return root;
}
//----------------------------------function---------------------------------//
void insert_into_tree(int num,struct Node *&root)
{
    if (root==NULL)
    {
        root=new (nothrow) struct Node;
        check_allocated(root);
        root->_data=num;
        root->_left=root->_right=NULL;

    }
    else if(num<=root->_data)
        insert_into_tree(num,root->_left);
    else
        insert_into_tree(num,root->_right);
}
//----------------------------------function---------------------------------//
const Node *min_depth_leaf(const struct Node*root)
{
   const Node *leaf;

    int counter=0;
    int temp_counter=-1;

    closest_leaf_to_root(root,counter,temp_counter,leaf);

    return leaf;
}
//----------------------------------function---------------------------------//
void closest_leaf_to_root(const Node *root,int counter,int temp_counter,
                          const Node *leaf)
{
    if(leaf==NULL)
        return;
}
//----------------------------------function---------------------------------//
void free_tree(struct Node *root)
{
    if (root!=NULL)
    {
        free_tree(root->_left);
        free_tree(root->_right);
        delete root;
    }
}
//----------------------------------function---------------------------------//
void check_allocated(const struct Node *root)
{
    if(root==NULL)
    {
        cerr<<"cannot allocate meomry"<<endl;
        exit(EXIT_FAILURE);

    }
}

[JLBorges]

> this function is supposed to find the closest leaf to the root and it should be recursive(I think)


Do a breadth-first traversal of the tree and return first leaf node that is encountered.
It can be recursive; here is a non-recursive version:

#include <queue>

struct node { int value = 0 ; node* left = nullptr ; node* right = nullptr ; };

bool is_leaf( const node* n ) { return n && n->left == nullptr && n->right == nullptr ; }

// the closest leaf to the root of a binary tree.
const node* min_depth_leaf( const node* n )
{
    if( n == nullptr ) return nullptr ;

    std::queue< const node* > queue ;
    queue.push(n) ;

    while( !queue.empty() ) // BFS
    {
        const node* p = queue.front() ;
        if( is_leaf(p) ) return p ;

        queue.pop() ;
        if( p->left ) queue.push( p->left ) ;
        if( p->right ) queue.push( p->right ) ;
    }

    return nullptr ;
}

[user42]

can you show me how to do it without using queue and nullptr?

[JLBorges]

> without using queue and nullptr?

Aha! To be submitted to a career teacher, is it?
So we need to program as if we are still is the previous century, and as if C++ does not have a standard library.

Doing a breadth-first traversal without using any queue (standard or home-grown) is hard.
Here's an in-order traversal of the tree (recursive), keeping track of the depths at which the leaf nodes were encountered; and we return the one that was found at the lowest depth. (Obviously, this is not as efficient as doing a breadth-first traversal and terminating the traversal at the fist leaf that is encountered.)

Caveat: untested (legacy c++: we use a literal 0 for a null pointer)

struct node { int value ; node* left ; node* right ; /* constructor */ };

bool is_leaf( const node* n ) { return n && n->left == 0 && n->right == 0 ; }

struct dl_pair // pair holding leaf and the depth at which it was found
{
    int depth ;
    const node* leaf ;
    dl_pair( int d, const node* n ) : depth(d), leaf(n) { /* assert( is_leaf(leaf) ; */ }
};

dl_pair closest_leaf( const node* n )
{
    if( is_leaf(n) ) return dl_pair( 0, n ) ; // this node is a leaf, at depth == 0

    if( n->left && n->right ) // both left and right children are present
    {
        dl_pair left = closest_leaf(n->left) ;
        dl_pair right = closest_leaf(n->right) ;

        // depth from n is one greater than the depth from child nodes
        ++left.depth ;
        ++right.depth ;

        // return the one that was found at the smaller depth
        return right.depth < left.depth ? right : left ;
    }

    else // either left child or right child is not present
    {
        // return the closest leaf of the child that is present
        dl_pair dlp = closest_leaf( n->left ? n->left : n->right ) ;
        ++dlp.depth ; // depth from n is one greater
        return dlp ;
    }
}

// the closest leaf to the root of a binary tree.
const node* min_depth_leaf( const node* n )
{
    if( n == 0 ) return 0 ;
    else return closest_leaf(n).leaf ;
}

[user42]

It's only because I don't know what queue is

[JLBorges]

std::queue http://en.cppreference.com/w/cpp/container/queue
Tutorial: http://cpp-tutorial.cpp4u.com/STL_queue.html

[user42]

ok thanks I will have a look at that
another question
what is dl_pair?

[benhart]

I would take a better check with binary trees as those can get a bit complicated sometimes and it can leads to errors. Those errors can be dealt with programs such as checkmarx and others. But there are a lot of good guides among the web you can use.
Good luck.

[user42]

ok. thanks!