Embercode: AI-powered software engineer course

A forest ranger maps a park's trail system as a tree. The first trail starts at the ranger station, which is the root. Every junction splits a trail into a left branch and a right branch. A **leaf** is a trail end with no branches after it. The ranger wants to know how many trail ends there are, so she can place one signpost at each.

Print the number of leaves in the tree.

**Constraints:** 0 <= N <= 5000. Each value is an integer from -1000 to 1000.

Input. First line: N, the number of entries in the list (0 for an empty tree). Second line: the N entries, separated by spaces. The first entry is the root. After it come the children, row by row from the top, and each parent's left child before its right child. An entry `null` means that position has no node. The list may stop after the last real node. A node is a leaf when both of its children are `null`.

Output. One integer: the number of leaves.

Example 1 input

7
1 2 3 4 5 null 6

Output

Example 2 input

Output

LanguageC#

using System;
using System.Collections.Generic;
using System.Linq;

class TreeNode
{
    public int Val;
    public TreeNode? Left;
    public TreeNode? Right;

public TreeNode(int val)
    {
        Val = val;
    }
}

static class TreeBuilder
{
    // Builds a tree from the level-order list. "null" marks a missing child.
    public static TreeNode? Build(string[] entries)
    {
        if (entries.Length == 0 || entries[0] == "null")
        {
            return null;
        }
        var root = new TreeNode(int.Parse(entries[0]));
        var pending = new Queue<TreeNode>();
        pending.Enqueue(root);
        int idx = 1;
        while (pending.Count > 0 && idx < entries.Length)
        {
            TreeNode cur = pending.Dequeue();
            if (entries[idx] != "null")
            {
                cur.Left = new TreeNode(int.Parse(entries[idx]));
                pending.Enqueue(cur.Left);
            }
            idx++;
            if (idx < entries.Length && entries[idx] != "null")
            {
                cur.Right = new TreeNode(int.Parse(entries[idx]));
                pending.Enqueue(cur.Right);
            }
            idx++;
        }
        return root;
    }
}

class Program
{
    static int Leaves(TreeNode? node)
    {
        // your code here
        return 0;
    }

static void Main()
    {
        string[] tokens = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries);
        int n = int.Parse(tokens[0]);
        TreeNode? root = TreeBuilder.Build(tokens.Skip(1).Take(n).ToArray());
        Console.WriteLine(Leaves(root));
    }
}

Binary Trees: coding problems