Table of Contents
Understanding Questions
Traversal using depth-first search
Example
Output
in conclusion
Home Backend Development C++ The number of isosceles triangles in a binary tree

The number of isosceles triangles in a binary tree

Sep 05, 2023 am 09:41 AM
quantity Binary tree isosceles triangle

Binary tree is a data structure in which each node can have up to two child nodes. These children are called left children and right children respectively. Suppose we are given a parent array representation, you have to use it to create a binary tree. A binary tree may have several isosceles triangles. We have to find the total number of possible isosceles triangles in this binary tree.

In this article, we will explore several techniques to solve this problem in C.

Understanding Questions

Gives you a parent array. You have to represent it in the form of a binary tree so that the array index forms the value of the tree node and the value in the array gives the parent node of that particular index.

Please note that -1 is always the root parent node. Given below is an array and its binary tree representation.

Parent array = [0, -1, 3, 1, 1, 2, 2, 3, 4, 4]
Copy after login

Binary tree -

The number of isosceles triangles in a binary tree

In any binary tree, we can have three types of isosceles triangles -

  • Left Isosceles Triangle In this triangle, the vertex is a left The child node of the parent node, and the vertices forming the base (both sides of the isosceles triangle) are the left child nodes of the vertex. Child nodes can be direct or indirect. In the tree above, we have two such isosceles triangles - (2, 6, 3), (3, 7, 1).

  • Right Isosceles Triangle In this triangle, the vertex is rightChildren of the parent, while the vertices forming the base are the right children of the vertices. Children can be direct or indirect. In the tree above, we have only one such isosceles triangle (4, 1, 8).

  • Balanced Isosceles Triangle In this triangle, the vertices forming the base are the left and right child nodes of the vertex node. In the tree above, we have five such isosceles triangles (1, 3, 4), (3, 2, 7), (4, 8, 9), (2, 5, 6), (1, 2, 9)

Therefore, for the above binary tree, we have a total of 8 isosceles triangles.

Depth First Search (DFS) is a method of traversing all nodes of a tree in a depth manner. It starts at the root node, moves to each branch, and then backtracks.

  • First, we use DFS to traverse each node of the binary tree and convert it into a graph so that each node is represented as adjacent to each other. This makes traversal easier.

  • For each node, we check whether it has child nodes. After checking, we use the sort(node[x].begin(), node[x].end()) function to sort them.

  • Next, we check whether the current node is the left or right successor of its corresponding parent node. We use the DFS function recursively on all nodes of the binary tree.

  • If the current node has two children (either directly or indirectly), we check the possibility that an isosceles triangle exists by calculating the edges between them. We will find the edges between them through the graph function given in the code below.

  • Finally, we calculate the total number of isosceles triangles by adding up all possible triangles in different positions.

Example

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

#define MAX int(1e5)
vector < int > * node;
int right_down[MAX];
int right_up[MAX];
int left_down[MAX];
int left_up[MAX];

// DFS traversal over a node
void DFS(int x, int * parent) {
   // Check if adjacent nodes are present for node x
   if (node[x].size() != 0)
      sort(node[x].begin(), node[x].end());

   // Check whether the node has a parent node
   if (parent[x] != -1) {
      int indexOfParent = parent[x];
      int childrenCount = node[indexOfParent].size();

      if (childrenCount > 1) {
         int parentFirstChild = node[indexOfParent][0];

         // Check if current node is left node of the parent
         if (x == parentFirstChild) {
            right_up[x] += right_up[indexOfParent] + 1;
            // Check if current node is right node of the parent  
         } else {
            left_up[x] += left_up[indexOfParent] + 1;
         }
      } else {
         right_up[x] += right_up[indexOfParent] + 1;
      }
   }

   // Iterate over children of current node  
   for (int i = 0; i < node[x].size(); ++i) {
      int y = node[x][i];
      DFS(y, parent);

      // left child of current node
      if (i == 0) {
         left_down[x] += left_down[y] + 1;
      }
      // right child of current node
      else {
         right_down[x] += right_down[y] + 1;
      }
   }
}

int graph(int * parent, int N) {
   int rootNode;
   node = new vector < int > [N];

   for (int i = 0; i < N; ++i) {
      if (parent[i] != -1) {
         node[parent[i]].push_back(i);
      } else {
         rootNode = i;
      }

      left_up[i] = 0;
      right_up[i] = 0;
      left_down[i] = 0;
      right_down[i] = 0;
   }
   return rootNode;
}

int main() {
   int N = 10;
   int parent[] = { 0, -1, 3, 1, 1, 2, 2, 3, 4, 4 };
   int rootNode = graph(parent, N);
   DFS(rootNode, parent);
   int count = 0;
   // Counting the total isosceles triangles
   for (int i = 0; i < N; ++i) {
      count += min(right_down[i], right_up[i]);
      count += min(left_down[i], left_up[i]);
      count += min(left_down[i], right_down[i]);
   }
   cout << "Number of isosceles triangles in the binary tree are " <<
      count;
   return 0;
}
Copy after login

Output

Number of isosceles triangles in the binary tree are 8
Copy after login

in conclusion

We have discussed how to find the total number of equilateral triangles in a binary tree when given a parent array. We can achieve this by using depth-first search, which allows us to traverse a binary tree.

The above is the detailed content of The number of isosceles triangles in a binary tree. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
1 months ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

OpenOOD update v1.5: Comprehensive and accurate out-of-distribution detection code library and testing platform, supporting online rankings and one-click testing OpenOOD update v1.5: Comprehensive and accurate out-of-distribution detection code library and testing platform, supporting online rankings and one-click testing Jul 03, 2023 pm 04:41 PM

Out-of-distribution (OOD) detection is crucial for the reliable operation of open-world intelligent systems, but current object-oriented detection methods suffer from "evaluation inconsistencies" (evaluation inconsistencies). Previous work OpenOODv1 unifies the evaluation of OOD detection, but still has limitations in scalability and usability. Recently, the development team once again proposed OpenOODv1.5. Compared with the previous version, the new OOD detection method evaluation has been significantly improved in ensuring accuracy, standardization and user-friendliness. Image Paper: https://arxiv.org/abs/2306.09301OpenOODCodebase:htt

Increase your knowledge! Machine learning with logical rules Increase your knowledge! Machine learning with logical rules Apr 01, 2023 pm 10:07 PM

On the precision-recall curve, the same points are plotted with different axes. Warning: The first red dot on the left (0% recall, 100% precision) corresponds to 0 rules. The second dot on the left is the first rule, and so on. Skope-rules uses a tree model to generate rule candidates. First build some decision trees and consider the paths from the root node to internal nodes or leaf nodes as rule candidates. These candidate rules are then filtered by some predefined criteria such as precision and recall. Only those with precision and recall above their thresholds are retained. Finally, similarity filtering is applied to select rules with sufficient diversity. In general, Skope-rules are applied to learn the root cause of each

Print left view of binary tree in C language Print left view of binary tree in C language Sep 03, 2023 pm 01:25 PM

The task is to print the left node of the given binary tree. First, the user will insert data, thus generating a binary tree, and then print the left view of the resulting tree. Each node can have at most 2 child nodes so this program must iterate over only the left pointer associated with the node if the left pointer is not null it means it will have some data or pointer associated with it otherwise it will be printed and displayed as the left child of the output. ExampleInput:10324Output:102Here, the orange node represents the left view of the binary tree. In the given graph the node with data 1 is the root node so it will be printed and instead of going to the left child it will print 0 and then it will go to 3 and print its left child which is 2 . We can use recursive method to store the level of node

Detailed explanation of binary tree structure in Java Detailed explanation of binary tree structure in Java Jun 16, 2023 am 08:58 AM

Binary trees are a common data structure in computer science and a commonly used data structure in Java programming. This article will introduce the binary tree structure in Java in detail. 1. What is a binary tree? In computer science, a binary tree is a tree structure in which each node has at most two child nodes. Among them, the left child node is smaller than the parent node, and the right child node is larger than the parent node. In Java programming, binary trees are commonly used to represent sorting, searching and improving the efficiency of data query. 2. Binary tree implementation in Java In Java, binary tree

How to find the number of parameters provided by runtime in Java? How to find the number of parameters provided by runtime in Java? Sep 23, 2023 pm 01:13 PM

In Java, one way to pass parameters at runtime is to use the command line or terminal. When retrieving these values ​​for command line parameters, we may need to find the number of parameters provided by the user at runtime, which can be achieved with the help of the length attribute. This article aims to explain the process of passing and getting a user-supplied number of parameters with the help of a sample program. Get the number of arguments provided by the user at run time Before finding the number of command line arguments, our first step is to create a program that allows the user to pass arguments at run time. String[] parameter When writing Java programs, we often encounter the main() method. When the JVM calls this method, the Java application starts executing. It is used with an argument called String[]args

Linux command: How to check the number of telnet processes Linux command: How to check the number of telnet processes Mar 01, 2024 am 11:39 AM

Linux commands are one of the indispensable tools in the daily work of system administrators. They can help us complete various system management tasks. In operation and maintenance work, sometimes it is necessary to check the number of a certain process in the system in order to detect problems and make adjustments in time. This article will introduce how to use Linux commands to check the number of telnet processes, let us learn together. In Linux systems, we can use the ps command combined with the grep command to view the number of telnet processes. First, we need to open a terminal,

In C language, print the right view of the binary tree In C language, print the right view of the binary tree Sep 16, 2023 pm 11:13 PM

The task is to print the right node of the given binary tree. First the user will insert data to create a binary tree and then print a right view of the resulting tree. The image above shows a binary tree created using nodes 10, 42, 93, 14, 35, 96, 57 and 88, with the nodes on the right side of the tree selected and displayed. For example, 10, 93, 57, and 88 are the rightmost nodes of the binary tree. Example Input:1042931435965788Output:10935788 Each node has two pointers, the left pointer and the right pointer. According to this question, the program only needs to traverse the right node. Therefore, the left child of the node does not need to be considered. The right view stores all nodes that are the last node in their hierarchy. Therefore, we can

Write a code using C++ to find the number of subarrays with the same minimum and maximum values Write a code using C++ to find the number of subarrays with the same minimum and maximum values Aug 25, 2023 pm 11:33 PM

In this article, we will use C++ to solve the problem of finding the number of subarrays whose maximum and minimum values ​​are the same. The following is an example of the problem −Input:array={2,3,6,6,2,4,4,4}Output:12Explanation:{2},{3},{6},{6},{2 },{4},{4},{4},{6,6},{4,4},{4,4}and{4,4,4}arethesubarrayswhichcanbeformedwithmaximumandminimumelementsame.Input:array={3,3, 1,5,

See all articles