Deepest left leaf node in a binary tree | GeeksforGeeks

Deepest left leaf node in a binary tree | GeeksforGeeks

Given a Binary Tree, find the deepest leaf node that is left child of its parent. For example, consider the following tree. The deepest left leaf node is the node with value 9.

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

The idea is to recursively traverse the given binary tree and while traversing, maintain “level” which will store the current node’s level in the tree. If current node is left leaf, then check if its level is more than the level of deepest left leaf seen so far. If level is more then update the result. If current node is not leaf, then recursively find maximum depth in left and right subtrees, and return maximum of the two depths.

class Level

{

    // maxlevel: gives the value of level of maximum left leaf

    int maxlevel = 0;

}

    // A utility function to find deepest leaf node.

    // lvl:  level of current node.

    // isLeft: A bool indicate that this node is left child

    void deepestLeftLeafUtil(Node node, int lvl, Level level,

            boolean isLeft)

    {

        // Base case

        if (node == null)

            return;

  

        // Update result if this node is left leaf and its level is more

        // than the maxl level of the current result

        if (isLeft != false && node.left == null && node.right == null

                && lvl > level.maxlevel)

        {

            result = node;

            level.maxlevel = lvl;

        }

  

        // Recur for left and right subtrees

        deepestLeftLeafUtil(node.left, lvl + 1, level, true);

        deepestLeftLeafUtil(node.right, lvl + 1, level, false);

    }

  

    // A wrapper over deepestLeftLeafUtil().

    void deepestLeftLeaf(Node node)

    {

        Level level = new Level();

        deepestLeftLeafUtil(node, 0, level, false);

    }

http://algorithms.tutorialhorizon.com/find-the-deepest-left-node-in-a-binary-tree/
Find the Deepest Left Node in a Binary Tree.

• Take two global vari­able as “deep­estlevel” and ” deepLeft­N­ode”.
• start­ing with level=0, Do the inorder tra­ver­sal and when­ever you go down one level ( root.left OR root.right), increase the level by 1.
• Keep check­ing if cur­rent node is the left child and deep­estlevel < level, if yes then update the “deep­estlevel ” and ”deepLeft­N­ode “.
• At the end return ” deepLeft­N­ode “, which will the deep­est node value.

public int deepestLevel = 0;
public int deepLeftNode;

public int deepLeft(Node root) {
  find(root, 0, true);
  return deepLeftNode;
}

public void find(Node root, int level, boolean left) {
  if (root != null) {
    find(root.left, level+1, true);
    if (left && deepestLevel < level) {// check if it a left child and
          // current level is greater than deepest level
      deepLeftNode = root.data; // update the deepest left node
      deepestLevel = level;   // update the deepest level
    }
    find(root.right, level+1, false);
  }
}
http://www.fgdsb.com/2015/01/17/deepest-left-node/

int deepest_left_node(TreeNode* root) {

int max_level = 0, ret = 0;



function<void(TreeNode*, int)> dfs = [&](TreeNode* r, int level) {

if(!r) return;



if(level > max_level) {

max_level = level;

ret = r->val;

}

dfs(r->left, level + 1);

dfs(r->right, level + 1);

};    

dfs(root, 1);

return ret;

}

http://algorithms.tutorialhorizon.com/find-the-deepest-node-in-a-binary-tree/
Given a binary tree, Find the deep­est node in it.
int deepestlevel;
int value;

public int Deep(Node root) {
  find(root, 0);
  return value;
}

public void find(Node root, int level) {
  if (root != null) {
    find(root.left, level+1);
    if (level > deepestlevel) {
      value = root.data;
      deepestlevel = level;
    }
    find(root.right, level+1);
  }
}
http://www.geeksforgeeks.org/find-deepest-node-binary-tree/

// maxLevel : keeps track of maximum level seen so far.

// res :  Value of deepest node so far.

// level : Level of root

void find(Node *root, int level, int &maxLevel, int &res)

{

    if (root != NULL)

    {

        find(root->left, ++level, maxLevel, res);

        // Update level and resue

        if (level > maxLevel)

        {

            res = root->data;

            maxLevel = level;

        }

        find(root->right, level, maxLevel, res);

    }

}

// Returns value of deepest node

int deepestNode(Node *root)

{

    // Initialze result and max level

    int res = -1;

    int maxLevel = -1;

    // Updates value "res" and "maxLevel"

    // Note that res and maxLen are passed

    // by reference.

    find(root, 0, maxLevel, res);

    return res;

}

Read full article from Deepest left leaf node in a binary tree | GeeksforGeeks