Binary tree - ischild function not working .

[Nuv]

I made a function to check if the child belongs to a parent ($node) or not. However its not working completely.If i include immediate children of the parent ($node) then the answer is yes otherwise it gives nothing (indicating it isnt the child) which is wrong. I think its because of recursive functions.Can someone please point out my mistake.

 

<?php
function ischild($node,$child)   //$node is parent to see if $child is its child or not.
  {
    $sql = "SELECT lchild,rchild FROM tree WHERE parent = '$node'";
    $execsql = mysql_query($sql);
    $array = mysql_fetch_array($execsql);
    
    if(($array['lchild']) == $child)
    {
   
      return "yes";
    }
    elseif (!empty($array['lchild']))
    {
        ischild($array['lchild'],$child);
    } 
    if($array['rchild'] == $child)
    {
        return "Yes";
    }
    elseif(!empty($array['rchild']))
    {
        ischild($array['rchild'],$child);
     }
   
  }  

[btherl]

What happens to the return value of the recursive calls?  And is the final result "yes" if either of the recursive calls returns "yes"?

[Nuv]

Well i am trying to count the left node and right node  added on a particular date under $node(parent). However i cannot make a proper function for that. (it would be nice if you would help me with it) what i am doing is to find all the nodes with that date and then find if it is the child of $node(parent) and then the display the count.

[btherl]

Just looking at ischild() for now - a child C is a child of node N iff:

 

1.  C is a the left child or right of N (you have implemented this already), or

2.  C is a child (recursively) of the left child or the right child of N (you have the calls here, but don't handle the return value)

 

So your recursive calls to ischild() need to handle the return value to implement that second rule.  There's a number of ways to do it.  The simplest is probably like this:

 

    elseif (!empty($array['lchild']))
    {
        $ischild = ischild($array['lchild'],$child);
        if ($ischild == "Yes") return "Yes";
    } 

 

And make the same change to the right child check.  That will make it so the return value of the recursive calls, which was being ignored before, are passed back to the caller of the initial call to ischild().

[Nuv]

Thanks. Nice explanation.

 

I am also having trouble displaying a binary tree level wise.Level 0 being $node(parent) , Level 1 being immediate children of $node etc. I made a function to gather the nodes in an array but i don't know how to utilize it to my advantage.

 

 <?php
function tree_gather($node)   //Function to calculate count
  {
    $sql = "SELECT lchild,rchild FROM tree WHERE parent = '$node'";
    $execsql = mysql_query($sql);
    $array = mysql_fetch_array($execsql);
    
    if(!empty($array['lchild']) || !empty($array['rchild']))
    {
   
      $child[] = $array['lchild'];
      $child[] = $array['rchild'];
      $child[] = tree_gather($array['lchild']);
      $child[] = tree_gather($array['rchild']);
      
    } 
     return $child;
  } ?> 

 

Output-

Array
(
    [0] => 2
    [1] => 3
    [2] => Array
        (
            [0] => 4
            [1] => 5
            [2] => Array
                (
                    [0] => 10
                    [1] => 11
                    [2] => 
                    [3] => 
                )

            [3] => Array
                (
                    [0] => 8
                    [1] => 9
                    [2] => 
                    [3] => 
                )

        )

    [3] => Array
        (
            [0] => 7
            [1] => 6
            [2] => Array
                (
                    [0] => 15
                    [1] => 14
                    [2] => 
                    [3] => 
                )

            [3] => Array
                (
                    [0] => 13
                    [1] => 12
                    [2] => 
                    [3] => 
                )

        )

)

 

[btherl]

Are you displaying it on text or some kind of markup like HTML, or some other method?

[Nuv]

I will be displaying it using <table>.

[btherl]

Have you decided how you will display it in the table?  Will you be using td elements to get the right spacing?

[Nuv]

Yeah i have already decided that. I will be placing it in <td> tag.

[btherl]

Can you give a bit more detail about how you're going to display the tree?

[Nuv]

Hi,

 

Displaying will be normal in tables like if i enter level 1.Then it will show data like

 

Sr No.    Member id    Member name    Position

1.              3343              Drake                Left

2.              3435              Rob                    Right

 

 

Easy. Not too complicated. Its just the levels. How to show the members level wise. And how can i use my function. "(

[btherl]

Does the order in which the nodes are printed matter?  In any case, you can use a recursive function which keeps track of depth in the tree to find the depth of each node.  Whenever the recursive function calls itself for a lower node in the tree it calls itself with $depth+1 as an argument.  And the initial call will start with depth 1.  eg

 

function print_tree($tree) {
   print_tree_depth($tree, 1);
}

function print_tree_depth($tree, $depth) {
  # print current node
  print_tree_depth(left child, $depth+1);
  print_tree_depth(right child, $depth+1);
}

}

[Nuv]

Does the order in which the nodes are printed matter?  In any case, you can use a recursive function which keeps track of depth in the tree to find the depth of each node.  Whenever the recursive function calls itself for a lower node in the tree it calls itself with $depth+1 as an argument.  And the initial call will start with depth 1.  eg

 

function print_tree($tree) {
   print_tree_depth($tree, 1);
}

function print_tree_depth($tree, $depth) {
  # print current node
  print_tree_depth(left child, $depth+1);
  print_tree_depth(right child, $depth+1);
}

}

 

Is $tree the node ?

Also, Consider the following tree with node A(level 0) has immediate child,right child = C and left child = B (level 1 constitutes B and C). D,E and F become level 2 and so on.

    |-------A------|                     <--- Level 0
|--B--|         |--C--|                  <--- Level 1
D     E         F                           <--- Level 2

 

So if i want to see level 2 the function will fetch all the elements of level 2 i.e D, E and F only.Was i wrong in explaining it earlier or your function does the same ?

[btherl]

My function prints the nodes out in the order it finds them.  That will be A, B, D, E, C, F in your example tree.  It will always print the left child first.

 

What order do you want to print them in?

[btherl]

What order do you want to print them in?

 

This is why I haven't replied yet.  There is no point in me writing a function to print out the tree, and then have you say it's in the wrong order.  In your previous post you mentioned wanting to print out all nodes on a specific level as well.  Can you please clarify what it is that you want the function to do.

 

For example: "Function arguments are $tree and $depth.  Function prints out all nodes at level $depth, from left to right"

[Nuv]

Sequence really doesnt matter. However, from left to right should do.

[sasa]

you can binary tree put in array in this way

1. root node put on index 1 in array

2. lchild of node with index n put in array element with indeks 2*n

3. rchild of node with index n put in array element with indeks 2*n+1

 

parent element of element with index n is in position (int)(n/2)

 

level of element with index n is log(n, 2) (root element is level 0)

 

on n-th level is elements with index from pow(2, n) to pow(2, n+1)-1

 

here is code for put tree in array

 <?php
function tree_gather($node)   //Function to calculate count
  {
    $tree = array(1 => $node);
    b_tree($node, 1, &$tree);
    return $tree;
  } 
  function b_tree($node, $index, &$tree){
      $sql = "SELECT lchild,rchild FROM tree WHERE parent = '$node'";
      $execsql = mysql_query($sql);
      if($array = mysql_fetch_array($execsql)){
          if(!empty($array['lchild'])){
              $tree[$index * 2] = $array['lchild'];
              b_tree($array['lchild'], $index * 2, &$tree);
          }
          if(!empty($array['rchild'])){
              $tree[$index * 2 + 1] = $array['rchild'];
              b_tree($array['rchild'], $index * 2 + 1, &$tree);
          }
      }
  }
  ?>

the code is not tested

[btherl]

Since tree_gather() already traverses the whole tree, you can add code in it to track the levels and display each node as it goes.

 

 <?php
function tree_gather($node, $level)   //Function to calculate count
  {
    # SQL to fetch node data here
    print "[$level] - Display node data here\n";

    $sql = "SELECT lchild,rchild FROM tree WHERE parent = '$node'";
    $execsql = mysql_query($sql);
    $array = mysql_fetch_array($execsql);
    
    if(!empty($array['lchild']) || !empty($array['rchild']))
    {
   
      $child[] = $array['lchild'];
      $child[] = $array['rchild'];
      $child[] = tree_gather($array['lchild'], $level + 1);
      $child[] = tree_gather($array['rchild'] $level + 1);
      
    } 
     return $child;
  } ?> 

[Nuv]

Thanks both of you !