The number of nodes in a binary tree that has only a left child

Question

How to find the number of nodes in a binary tree that has only a left child?

LeftNode(root)
{
    if(root==NULL) 
        return 0;

    if(root->left!=null && root-right==null)
        return (1+LeftNode(root->left));

    return (LeftNode (root->left) + LeftNode (root->right))
}

Answer 1

I would do this (C ++):

int leftNode(Node * root)
{
  if (root == nullptr)
    return 0;

  // c is 1 if root has a left child and has not a right one
  int c = root->left != nullptr and root->right == nullptr ? 1 : 0;

  return c + leftNode(root->left) + leftNode(root->right);
}

Answer 2

Since no specific language is required, I'm going to write my solutions in Swift

func nodesWithOnlyLeftChild(node:Node?) -> UInt {
    guard let node = node else { return 0 }
    let count: Uint = (node.left != nil && node.right == nil) ? 1 : 0
    return nodesWithOnlyLeftChild(node.left) + nodesWithOnlyLeftChild(node.right) + count
}

Explaination

1: signature

func nodesWithOnlyLeftChild(node:Node?) -> UInt

The function takes a type parameter Node?. This means that the parameter can be Nodeor nil. The function returns an unsigned integer.

2: parameter check

guard let node = node else { return 0 }

On the first line, check that the input parameter is not nil. If it is not nil, then the next line is executed, otherwise it is returned 0.

3: Assess the current node

let count: UInt = (node.left != nil && node.right == nil) ? 1 : 0

count. 1, node . 0 .

4:

return nodesWithOnlyLeftChild(node.left) + nodesWithOnlyLeftChild(node.right) + count

nodesWithOnlyLeftChild, + nodesWithOnlyLeftChild, + count

O(n), n - .

O(1). Infact, n , Tail Recursion ( LLVM ) , .